Форум программистов, компьютерный форум 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" Что ему тут не нравится -- ума не приложу. Все функции есть в хидере, ругаться стал недавно -- ранее работал на ура. Перестраивала, перезапускала блокс(на всяк пожарный), а толку нет. Вот сам код: #include "HW_C.h" void less_1() { bool flag=true; int temp; system("clear"); ... http://www.cyberforum.ru/cpp-beginners/thread1059634.html
C++ Чтение определенного количества строк
Помогите, пожалуйста, с функцией, чтобы можно было из файла считать определенное кол-во строк и запихнуть их все в одну переменную
C++ Ошибка : слишком много включаемых файлов
Здравствуйте! Помогите, пожалуйста, исправить ошибку( С1014 слишком много включаемых файлов). Не знаю, где лишние .h файлы убрать. Вроде они везде нужны, но какая-то цикличность потом получается... //main #include "stdafx.h" #include <iostream> #include "conio.h" #include "Desk.h"
C++ Не удается найти указанный файл http://www.cyberforum.ru/cpp-beginners/thread1059620.html
После переустановки винды скачал DEV C++. Начал решать задачу, решил вроде бы правильно, но выдало ошибку - "Не удается найти указанный файл.". Подумал что не так решил, написал простой хеллоуворлд и та же снова ошибка. Скачал КодеБлок, все то же самое. Скачал уж под худой конец Visual Studio. Блин, опять то же самое. .net framework 4 есть на компе. Искал я и на форуме да и гуглил, но...
C++/CLI WinForms PinnBall первые неполадки Приветствую! Пишу пин бол, но уже появилась первая проблема. Не могу перехватить клавишу. Пробовал несколько способов и все безтолку. e->KeyCode = a Key = a e->KeyCode = Key->a Гуглить тоже пытался, но безуспешно. подробнее

Показать сообщение отдельно
ilya-sin
0 / 0 / 0
Регистрация: 28.12.2013
Сообщений: 6
28.12.2013, 22:54     Поиск максимального паросочетания методом беллмана-форда
Помогите написать программу для поиска максимального паросочетания методом беллмана-форда. На сколько я понимаю этот алгоритм ищет минимальный путь между вершинами. Тогда как я должен его использовать для поиска максимального паросочетания? Вот мои старания:
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");
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 12:02. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru