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

Поиск максимального паросочетания методом беллмана-форда - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Изменение массива http://www.cyberforum.ru/cpp-beginners/thread1059662.html
Вставить в массив два числа следующим образом: первое со значением N перед всеми элементами, большими N, и второе со значением M – после всех элементов, меньших М. Каков должен быть максимальный...
C++ Как изменить код, чтобы не было ошибки "expected initializer before void" В общем, компилятор почему-то ругается на 3 строку, говоря "expected initializer before void" Что ему тут не нравится -- ума не приложу. Все функции есть в хидере, ругаться стал недавно -- ранее... http://www.cyberforum.ru/cpp-beginners/thread1059634.html
C++ Чтение определенного количества строк
Помогите, пожалуйста, с функцией, чтобы можно было из файла считать определенное кол-во строк и запихнуть их все в одну переменную
C++ Ошибка : слишком много включаемых файлов
Здравствуйте! Помогите, пожалуйста, исправить ошибку( С1014 слишком много включаемых файлов). Не знаю, где лишние .h файлы убрать. Вроде они везде нужны, но какая-то цикличность потом получается......
C++ Не удается найти указанный файл http://www.cyberforum.ru/cpp-beginners/thread1059620.html
После переустановки винды скачал DEV C++. Начал решать задачу, решил вроде бы правильно, но выдало ошибку - "Не удается найти указанный файл.". Подумал что не так решил, написал простой хеллоуворлд и...
C++ просьба просто скомпилить и запустить код просьба просто скомпилить и запустить код (в любой IDE) т.к. товарисч говорит, что в той же IDE что и у меня он этого сделать не может... Интересует чтобы просто прога работала от начала до конца ... подробнее

Показать сообщение отдельно
ilya-sin
0 / 0 / 0
Регистрация: 28.12.2013
Сообщений: 6

Поиск максимального паросочетания методом беллмана-форда - C++

28.12.2013, 22:54. Просмотров 397. Ответов 0
Метки (Все метки)

Помогите написать программу для поиска максимального паросочетания методом беллмана-форда. На сколько я понимаю этот алгоритм ищет минимальный путь между вершинами. Тогда как я должен его использовать для поиска максимального паросочетания? Вот мои старания:
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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include "stdafx.h"
#include <iostream>
#include <map>
#include <vector>
#include <set>
#include <stack>
#include <fstream>
#define inf 100000
 
using namespace std;
 
typedef int Vertex;
typedef int WeightType;
typedef int Potok;
typedef map<Vertex, WeightType> Connection;
typedef Connection *Connections;
typedef vector <Connections> Graph;     //вектор из мэпов
 
struct Edge                         //ребро
{
    Vertex v1,v2;
    WeightType weight;  //пропускная способность
    bool orientation;
    Edge (Vertex _v1, Vertex _v2, WeightType _weight, bool _orientation)
    {
        this->v1 = _v1;
        this->v2 = _v2;
        this->weight = _weight;
        this->orientation = _orientation;
    }
};
 
Graph *CreateGraph(int N)           //создание графа
{
    Graph *graph = new Graph(N + 2);
    for (int i = 0; i < N + 2; ++i)
        (*graph)[i] = new Connection;
    return graph;
}
 
int AddEdge (Graph *graph, Edge edge)       //добавить ребро
{
    (*(*graph)[edge.v1])[edge.v2] = edge.weight;
    if (!edge.orientation)
        (*(*graph)[edge.v2])[edge.v1] = edge.weight;
    return 0;
}
 
void Bellman_Ford (Graph *graph, int N, Vertex S)
{
    int *d = new int[N];
    int p[100];
    for (int i = 0; i < N; i++)
        d[i] = inf;
    d[S] = 0;
    for (int i = 0; i < N - 1; i++)
    {
        for (int k = 0; k < N; k++)
        {
            for ( map<Vertex, WeightType>::iterator j = (*(*graph)[k]).begin(); j != (*(*graph)[k]).end(); ++j)
            {
                if (d[(*j).first] > d[k] + (*j).second)
                {
                    d[(*j).first] = d[k] + (*j).second;
                }
            }
        }
    }
 
    for (int i = 0; i < N; i++) 
        if (d[i] == inf)
             cout << endl << S << "->" << i << "=" << "Not";
        else cout << endl << S << "->" << i << "=" << d[i]; 
    cout << endl;
}
 
void main()
{
    setlocale(0,"");
    int N;
    ifstream f("GraphFile.txt");
    f.clear();      
    f.seekg(0);
    if (!f) 
        cout << "Ошибка чтения файла."<< endl;
    
    f >> N;
    Graph *graph = CreateGraph(N);
    set <Vertex> with_S, with_I;
    int M = 0;
    while (!f.eof()) 
    {
        Vertex v1,v2;
        WeightType w;
        bool orient;    
        f >> v1;
        with_S.insert(v1);      //вершины, соединяющиеся со стоком
        f >> v2;
        with_I.insert(v2);      //вершины, соединяющиеся с истоком
        f >> w;
        f >> orient;
        AddEdge(graph, Edge(v1, v2, w, true));
        M++;
    }
    
    Vertex S = N; 
    Vertex I = N + 1;
    N += 2;
 
    for (set <Vertex>::iterator i = with_S.begin(); i != with_S.end(); ++i)
        AddEdge(graph, Edge(S, *i, 1, true));
    
    for (set <Vertex>::iterator i = with_I.begin(); i != with_I.end(); ++i)
        AddEdge(graph, Edge(*i, I, 1, true));                               //сформировали транспортную сеть
 
    Bellman_Ford(graph, N, S);
 
    system("pause");
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru