С Новым годом! Форум программистов, компьютерный форум, киберфорум
Наши страницы

задача на систему дорог - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Графы (может ли данная матрица быть матрицей смежности простого неориентированного графа) http://www.cyberforum.ru/cpp-beginners/thread875395.html
По заданной квадратной матрице из нулей и единиц определите, может ли данная матрица быть матрицей смежности простого неориентированного графа помогите решить вот такую задачу пожалуйста(( По...
C++ СТРУКТУРЫ ДАННЫХ: ДЕРЕВЬЯ помогите пожалуйста вот с такой задачей(( 1. Написать программу подсчета числа вершин в бинарном дереве 2. Написать программу подсчета левых вершин бинарного дерева 3. Написать программу подсчета... http://www.cyberforum.ru/cpp-beginners/thread875394.html
C++ Стек/Разработать программу, реализующую алгоритм стека
Добрый. Помогите пжл написать программу по заданию: Разработать программу, реализующую алгоритм стека (20 элементов). Задача решается в двух вариантах: статическом (на основе массива структур)...
C++ модель сосредоточенной системы
нyжно сделать очень простyю модель сосредоточенной системы помогите пожалyйста
C++ удаление повторяющихся строк.исправить программу http://www.cyberforum.ru/cpp-beginners/thread875373.html
помогите исправить программу. задание: В магазине сформирован список постоянных клиентов, который включает ФИО, домашний адрес покупателя и размер предоставляемой скидки. Удалить из этого списка все...
C++ Структуры (данные о студентах) - вывод данных в файл Здравствуйте, у меня проблема с выводом данных в файл. При проверке нет ни каких замечаний, однако в файл не заносит инфы. Просмотрите на правильность всего кода. заранее благодарен. #include... подробнее

Показать сообщение отдельно
bolabol
0 / 0 / 0
Регистрация: 23.05.2013
Сообщений: 7
03.06.2013, 18:28  [ТС]
Цитата Сообщение от aram_gyumri Посмотреть сообщение
bolabol, вот решение алгоритмом Краскала с СНМ
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int parent[20000],rank[20000];
void dsu_make(int v)
{
    parent[v]=v;
    rank[v]=0;
}
int dsu_find(int v)
{
    if (parent[v]==v)
        return v;
    return parent[v]=dsu_find(parent[v]);
}
void dsu_unite(int a,int b)
{
    a=dsu_find(a);
    b=dsu_find(b);
    if (a!=b)
    {
        if (rank[a]<rank[b])
            swap(a,b);
        parent[b]=a;
        if (rank[a]==rank[b])
            ++rank[a];
    }
}
int main()
{
    int n,m,i,a,b,w,k;
    scanf("%d%d",&n,&m);
    vector<pair<int,pair<int,int> > > g;
    for (i=0;i<m;i++)
    {
        scanf("%d%d%d",&a,&b,&w);
        g.push_back(make_pair(w,make_pair(a-1,b-1)));
    }
    sort(g.begin(),g.end());
    for (i=0;i<n;i++)
        dsu_make(i);
    for (k=i=0;i<m;i++)
    {
        a=g[i].second.first;
        b=g[i].second.second;
        w=g[i].first;
        if (dsu_find(a)!=dsu_find(b))
        {
            k+=w;
            dsu_unite(a,b);
        }
    }
    printf("%d",k);
    return 0;
}
хмм спасибо !
НО все же хотелось бы прогу по алгоритму на графах, ото это сложновато для меня. Крускал проходил, а СНМ не помню
0
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.