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

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

Восстановить пароль Регистрация
Другие темы раздела
C++ Очередь на базе кольцевого массива http://www.cyberforum.ru/cpp-beginners/thread885198.html
Задание:Очередь как кольцевой массив. Записать стек в очередь. Я написала очередь на базе кольцевого массива и стек реализованный через массив, но не могу понять как мне записать мой стек в очередь. И можете пояснить , к примеру есть очередь 1 2 3 , и есть стек 9 8 , когда я запишу стек в очередь , она будет иметь вид : 1 2 3 8 9 или 1 2 3 9 8 ? #include<stdio.h> #include<stdlib.h>...
C++ нужна рекомендация с комментариями #include "stdafx.h" #include <iostream> #include <stdio.h> using namespace std; int main() { setlocale (LC_CTYPE, "Russian"); int N,M,c=0,max=0,f,i,j; int index=0; int A; http://www.cyberforum.ru/cpp-beginners/thread885193.html
C++ Pascal to c++
помогите перевести в с++ Procedure Min(a,b:real;Var max:real); Begin if a>b then max:=a else max:=b; End;
Работа с текстовым файлом (чтоб проверяло каждую строчку на палиндрому) C++
#include <conio.h> #include <iostream> #include <fstream> #include <iomanip> #include <stdlib.h> #include <string> #include <algorithm> using namespace std; bool ispalind(string s); int main()
C++ "const char" в "int" http://www.cyberforum.ru/cpp-beginners/thread885171.html
Всем привет, я новенький тут и сразу возник вопрос Делал все по видео уроку но ошибка все же появилась. #include <iostream> using namespace std;
C++ Преобразование в базовый класс Доброго времени суток Никак не получается разобраться с одним примером void fnc(); class CLASS1 { public: int r; }; class CLASS2:private CLASS1 { подробнее

Показать сообщение отдельно
HookMan007
0 / 0 / 0
Регистрация: 13.12.2011
Сообщений: 12
30.05.2013, 17:02     Поиск минимального остовного дерева в графе
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
#include <vector>
#include <queue> // Определяет классы priority_queue шаблона и очереди и несколько 
вспомогательных шаблонов
#include <iostream>
using namespace std;
 
typedef pair<int, int> a; //pair - список смежности хранящий, вершины; a - вес ребра
typedef vector<vector<a>> Graph;
 
long long func(Graph &g, vector<int> &pred) //
{
    int inf = 10000000;
    int n = g.size();
    pred.assign(n, -1);
    vector<bool> used(n); //вектор, использованных вершин
    vector<int> vector_rast(n, inf); //вектор расстояний
    vector_rast[0] = 0;
    priority_queue <a, vector<a> , greater<a>> q;
    q.push(make_pair(0, 0));
    long long res = 0;
 
    while (!q.empty()) {
        int start = q.top().first;
        int end = q.top().second;
        q.pop();
        if (used[end])
            continue;
        used[end] = true;
        res += start;
        for (int i=0; i<(int)g[end].size(); i++)
        {
            int v = g[end][i].first; //выбраем ребро из дерева в цикл с наименьшим весом
            if (used[v])
                continue;
            int vector_rast2 = g[end][i].second; //добавляем конец ребра к дереву
            if (vector_rast[v] > vector_rast2) { //изменяем цикл, для этого обновляем 
список ребер из дерева в цикле так, чтобы он состоял из ребер наименьшего веса
                vector_rast[v] = vector_rast2;
                pred[v] = end;
                q.push(make_pair(vector_rast2, v)); //добавляем в цикл вершины, соседние 
с новой
            }
        }
    }
    return res;
}
 
void main()
{
    setlocale (LC_ALL, "Russian");
        Graph g(5);
    g[0].push_back(make_pair(2, 4));
    g[2].push_back(make_pair(0, 4));
    g[0].push_back(make_pair(4, 7));
    g[4].push_back(make_pair(0, 7));
    g[1].push_back(make_pair(2, 4));
    g[2].push_back(make_pair(1, 4));
    g[2].push_back(make_pair(3, 5));
    g[3].push_back(make_pair(2, 5));
 
    Изменение:
    g[0].push_back(make_pair(2, 4));
    g[2].push_back(make_pair(0, 4));
    g[3].push_back(make_pair(4, 6));
    g[4].push_back(make_pair(3, 6));
    g[1].push_back(make_pair(2, 4));
    g[2].push_back(make_pair(1, 4));
    g[2].push_back(make_pair(3, 5));
    g[3].push_back(make_pair(2, 5));
 
    Конечный вариант:
    g[0].push_back(make_pair(2, 4));
    g[2].push_back(make_pair(0, 4));
    g[0].push_back(make_pair(1, 3));
    g[1].push_back(make_pair(0, 3));
    g[0].push_back(make_pair(3, 2));
    g[3].push_back(make_pair(0, 2));
    g[1].push_back(make_pair(4, 3));
    g[4].push_back(make_pair(1, 3));
 
    vector<int> vector_rast;
    long long result = func(g, vector_rast);
    cout << "Результат: " << result << endl;
    system("pause");
}
Добавлено через 5 минут
Помогите разобраться с кодом. Конкретно: для чего нужен pred.assign и что в вайле происходит
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 18:57. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru