Форум программистов, компьютерный форум CyberForum.ru

Поиск минимального остовного дерева на графе - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ Не компилируются проекты: Build: 0 succeeded, 1 failed, 0 up-to-date, 0 skipped http://www.cyberforum.ru/cpp-beginners/thread1240571.html
Здравствуйте, уважаемые специалисты. Недавно начал изучать С++ Компилятор Visual C++ при попытке скомпилировать любой код выдаёт это: ========== Build: 0 succeeded, 1 failed, 0 up-to-date, 0 skipped ========== Подскажите пожалуйста, в чем может быть проблема? Заранее спасибо.
C++ Конструктор копирования, аварийное завершение на этапе исполнения #include <iostream.h> #include <string.h> class String{ private: char *data; int max_length; public: String() { http://www.cyberforum.ru/cpp-beginners/thread1240568.html
C++ Будут ли все константы гарантированно инициализированы к моменту обращения к ним из разных единиц трансляции
Безопасно ли такое использование: // config.cpp const int ival = 6; const SomeNonTrivialClass obj(...); // config.h extern const int ival; extern const SomeNonTrivialClass obj; // some_source_file.cpp
Как реализовать свой тип данных C++
Здравсвтуйте,подскажите пожалуйста как реализовать с с++ свой тип данных. Допустим хочу завести массив,где каждому arr будет соответсвовать две переменные(arr.a,arr.b). Если точнее - arr.a,arr.b ... arr.a,arr.b. В дельфи такое делалось через type. Читал про структуры,но вроде это не то,что надо.
C++ Перегруженный operator<< http://www.cyberforum.ru/cpp-beginners/thread1240484.html
Есть допустим такая дружественная функция: объявление template<typename Type> friend std::ostream& operator<<(std::ostream&, Stack<Type>&); определение template<typename Type> std::ostream& operator<<(std::ostream& stream, Stack<Type>& obj_show) { Stack<Type>::node* ptr = obj_show.top;
C++ Вывести на экран суммарный результат, указав число студентов сдавших и проваливших экзамен День добрый помогите решить задачу: есть 10 студентов ( 10 раз на екран должно высвечиватся"Введите результат" результат- если пользователь пишет 1,значит студент сдал,если пишет 2 - провалил нужно -подсчитать число результатов каждого типа) -вывести на экран суммарный результат,указав число студентво здавших и проваливших -если хотя бы 8 студентов сдало тест написать "Отлично" подробнее

Показать сообщение отдельно
ZaMaZaN4iK
Мой лучший друг-отладчик!
 Аватар для ZaMaZaN4iK
163 / 163 / 9
Регистрация: 24.06.2012
Сообщений: 662
Записей в блоге: 5
Завершенные тесты: 1
16.08.2014, 02:09     Поиск минимального остовного дерева на графе
Я не знаю конечно, но может вам будет интересно это. Это алгоритм нахождения минимального остовного дерева алгоритмом Крускала (список рёбер):
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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
//Минимальное остовное дерево за O(NlogN) методом Краскала через DSU(систему непересекающихся множеств)
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <ctime>
#include <algorithm>
 
using namespace std;
typedef long long ll;
 
const ll maxn=100,maxm=200;//максимум вершин и максимум рёбер
vector<ll> d(maxn,-1);//массив для DSU
vector<pair<ll,pair<ll,ll> > > a(maxm),p;//тут будем хранить рёбра.Первый элемент - вес ребра, 2-ой и 3-ий - начало и конец ребра
ll i,j,k,z=0,temp,r,n,m;
 
//функция для получения корня данного множества.Подробное описание в описании самого DSU
 
ll findroot(ll v)
{
    return d[v]==-1 ? v : d[v]=findroot(d[v]);
}
 
//функция обьединения двух множеств.Подробное описание в описании самого DSU
 
bool union_set(ll a,ll b)
{
    ll q1,q2;
    q1=findroot(a);
    q2=findroot(b);
    if(q1 != q2)
    {
        r=rand() % 2;
        r==0 ? d[q1]=q2 : d[q2]=q1;
        return true;
    }
    return false;
}
 
//Задаем граф по кторому будем искать минимальный остов
 
void input()
{
    scanf("%I64d %I64d",&n,&m);
    for(i=0;i<m;++i)
    {
        scanf("%I64d %I64d %I64d",&a[i].second.first,&a[i].second.second,&a[i].first);
    }
}
 
//Главная функция алгоритма.Работает следующим образом: мы сортируем в порядке возрастания ребра по весу.Потом берем первые n-1 рёбер
//(так как дерево будет состоять из n-1 ребра по теореме о деревьях) и если концы не принадлежат одному множеству(то есть не соединены), то берем это ребро
//добавлем вес к минимальной стоимости дерева, и обьединяем концы ребра в одно множество.И так до тех пор, пока не запишем в ответ N-1 раз ребра.
//В данной реализации мы не минимальный вес получаем, а сами ребра, из которых будет состоять мимнимальное остовное дерево
 
void sol()
{
    sort(a.begin(),a.begin()+m);
    temp=n-1;
    for(i=0;i<m && z<temp;++i)
    {
        if(union_set(a[i].second.first,a[i].second.second))
        {
            ++z;
            p.push_back(a[i]);
        }
    }
}
 
//Вывод полученного дерева
 
void output()
{
    for(i=0;i<p.size();++i)
        printf("%I64d -> %I64d = %I64d\n",p[i].second.first,p[i].second.second,p[i].first);
}
 
//Ну а тут сначала обнуляем rand(), затем вводим граф, считаем min_ost и выводим его
 
int main()
{
    srand(time(0));
    input();
    sol();  
    output();  
    system("pause");
    return 0;
}
 
Текущее время: 19:52. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru