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

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

Восстановить пароль Регистрация
 
ilya-sin
0 / 0 / 0
Регистрация: 28.12.2013
Сообщений: 6
28.12.2013, 22:54     Поиск максимального паросочетания методом беллмана-форда #1
Помогите написать программу для поиска максимального паросочетания методом беллмана-форда. На сколько я понимаю этот алгоритм ищет минимальный путь между вершинами. Тогда как я должен его использовать для поиска максимального паросочетания? Вот мои старания:
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");
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
28.12.2013, 22:54     Поиск максимального паросочетания методом беллмана-форда
Посмотрите здесь:

Алгоритм Форда-Беллмана C++
C++ Алгоритм Габова для поиска максимального паросочетания в произвольном графе за O(V^3)
C++ Потоки и паросочетания
Алгоритм Форда - Беллмана C++
Поиск максимального елемента ,методом деления пополам C++
C++ Поиск максимального
C++ Матрица Форда Беллмана и метод Дейкстра
C++ Алгоритм Форда-Беллмана

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

Текущее время: 10:23. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru