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

Графы. Поток минимальной стоимости - C++

Восстановить пароль Регистрация
 
c++\noob
 Аватар для c++\noob
-2 / 2 / 0
Регистрация: 13.11.2010
Сообщений: 52
20.12.2012, 14:04     Графы. Поток минимальной стоимости #1
Помогите кто может сделать тестовый пример для данной программы. Что-то не выходит у меня с вводом и выводом: данные читаются из файла(Input), результат записывается в файл(Output).

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
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
#include <vector>
#include <algorithm>
 
using namespace std;
 
// это типа бесконечность будет
const int inf = 0x3fffffff;
 
/* структура, олицетворяющая одно ребро */
struct Edge
{
    int next;           // номер вершины, в которую идет ребро
    int inv;            // номер обратного к данному ребру ребра, нумерация конечно в списке вершины next
    int flow;           // текущий поток
    int cap;            // пропускная способность ребра
    int cost;           // стоимость потока по данному ребру
 
    /* конструктор - задаёт все параметры, кроме текущего потока, который
    выставляется сначала как нулевой */
    Edge(int next, int inv, int cap, int cost) : next(next), inv(inv), flow(0), cap(cap), cost(cost) {}
};
 
/* структура, олицетворяющая граф, с которым будем работать */
struct Graph
{
    int n;              // количество вершин в графе
    vector<vector<Edge> > e;    // исходящие ребра, соответственно по одному вектору ребер на каждую вершину
    vector<int> phi;        // вектор потенциалов, по одному потенциалу на каждую вершину :)
    vector<int> d;          // вектор текущих расстояний для алгоритма Дейкстры
    vector<int> f;          // вектор флажков для алгоритма Дейкстры
    vector<int> from;       // вектор, по которому восстанавливается путь после алгоритма Дейкстры; точное
                                                        // определение - номер ребра в списке ребер для данной вершины, по которому
                                                        // надо перейти, чтобы попасть в вершину-предшественника
 
    /* создать граф с n вершинами - просто инициализирует все векторы нужным количеством объектов */
    Graph(int n) : n(n), e(n), phi(n), d(n), f(n), from(n) {}
 
    /* добавить ребро графа; в действительности добавляет два ребра - прямое и обратное */
    void AddEdge(int a, int b, int cap, int cost)
    {
        // добавить прямое ребро
        e[a].push_back(Edge(b, e[b].size(), cap, cost));
        // добавить обратное ребро
        e[b].push_back(Edge(a, e[a].size() - 1, 0, -cost));
        /* почему inv для ребер устанавливается именно так? inv - это номера ребер в соответствующих
        векторах. В первой строке - e[b].size(), так как во второй строке новое ребро получит именно
        этот номер. Во второй строке - e[a].size() - 1, так как прямое ребро уже создано, и
        уже получило соответствующий номер */
    }
 
    /* Найти максимальный поток минимальной стоимости!!!
    source - номер вершины-истока, sink - номер вершины-стока
    возвращать результат будем в паре (поток; стоимость) */
    pair<int, int> MinCostMaxFlow(int source, int sink)
    {
        /* выполнить начальное назначение потенциалов
        с помощью алгоритма Беллмана-Форда.
        Проще говоря, начальные потенциалы вершин - это кратчайшие
        расстояния до вершин от истока, если считать длинами ребер
        их стоимости; причем учитываются только прямые ребра.
        Если ребер отрицательной стоимости в графе нет,
        то следующий блок можно (и нужно) выкидывать :) */
        {
            // залить потенциалы бесконечностями
            fill(phi.begin(), phi.end(), inf);
            // только истоку задать 0
            phi[source] = 0;
            // по алгоритму нужно все тупо повторить n раз
            for(int i = 0; i < n; ++i)
                // перебор вершины
                for(int j = 0; j < n; ++j)
                    // если она уже получила потенциал
                    if(phi[j] < inf)
                        // перебор исходящих из вершины ребер
                        for(int k = 0; k < e[j].size(); ++k)
                            // если ребро - прямое, и позволяет улучшить оценку расстояния до вершины на ее конце
                            if(e[j][k].cap > 0 && phi[e[j][k].next] > phi[j] + e[j][k].cost)
                                // улучшить эту оценку
                                phi[e[j][k].next] = phi[j] + e[j][k].cost;
        }
 
        // переменные для ответа
        int resultFlow = 0, resultCost = 0;
 
        /* вооот... только сейчас начинается основной алгоритм :)
        цикл, на каждой итерации которого выполняется поиск увеличивающего пути
        и собственно увеличение потока по этому пути */
        for(; ; )
        {
            // обнулить флажки
            fill(f.begin(), f.end(), 0);
            // установить расстояние до всех вершин равным бесконечности
            fill(d.begin(), d.end(), inf);
            // кроме, конечно, истока
            d[source] = 0;
 
            // цикл алгоритма Дейкстры
            for(; ; )
            {
                // найти непомеченную вершину с наименьшим расстоянием до истока
                int i = -1;
                for(int j = 0; j < n; ++j)
                    if(!f[j] && d[j] < inf && (i < 0 || d[i] > d[j]))
                        i = j;
                // если такой вершины нет, то, значит, все вершины или помечены, или недостижимы
                // завершаем алгоритм Дейкстры
                if(i < 0) break;
 
                // помечаем найденную вершину
                f[i] = 1;
 
                // перебираем исходящие из нее ребра
                for(int j = 0; j < e[i].size(); ++j)
                    // рассматриваем только те ребра, по которым можно протолкнуть поток
                    if(e[i][j].cap > e[i][j].flow)
                    {
                        // получить вершину на другом конце ребра
                        int a = e[i][j].next;
                        // проверить, что она непомечена, и можно улучшить оценку расстояния до нее
                        // расстояние проверяется с учетом потенциалов!
                        if(!f[a] && d[a] > d[i] + e[i][j].cost + phi[i] - phi[a])
                        {
                            // улучшаем оценку расстояния
                            d[a] = d[i] + e[i][j].cost + phi[i] - phi[a];
                            // указываем для нее вершину-предшественника (вернее, как уже говорилось,
                            // номер ребра, перейдя по которому, мы придем в предшественника)
                            from[a] = e[i][j].inv;
                        }
                    }
            }
 
            // все, алгоритм Дейкстры вычислил кратчайшие пути
            // если при этом он не дошел до стока, то, значит, увеличивающих
            // путей больше нет; завершаем алгоритм
            if(!f[sink]) break;
 
            // выполняем обновление потенциалов
            for(int i = 0; i < n; ++i)
                // в зависимости от того, достигнута ли вершина, прибавляем к ее потенциалу добавку
                phi[i] += f[i] ? d[i] : d[sink];
 
            // определяем, насколько мы на этот раз можем увеличить поток
            // и сколько нам это стоило
            int augFlow = inf, augCost = 0;
            // для этого надо пройтись по найденному увеличивающему пути
            // и поглядеть, сколько можно протолкнуть потока
            // так как у нас сохранены предшественники, то идем от стока к истоку
            // т.е. как бы задом наперед
            for(int i = sink; i != source; )
            {
                // получить вершину, из которой мы пришли в вершину i
                int a = e[i][from[i]].next;
                // получить ребро, по которому мы пришли из вершины a в вершину i
                int b = e[i][from[i]].inv;
 
                // ограничить новый поток, если надо
                // cap - flow - это максимальный добавочный поток, который мы
                // можем протолкнуть через данное ребро
                augFlow = min(augFlow, e[a][b].cap - e[a][b].flow);
                // суммировать стоимость потока
                augCost += e[a][b].cost;
 
                // перейти дальше "назад"
                i = a;
            }
 
            // теперь мы вычислили, сколько потока мы можем сейчас протолкнуть
            // скорректировать информацию в ребрах с помощью еще одного прохода
            for(int i = sink; i != source; )
            {
                // получить вершину, из которой мы пришли в вершину i
                int a = e[i][from[i]].next;
                // получить ребро, по которому мы пришли из вершины a в вершину i
                int b = e[i][from[i]].inv;
 
                // добавить поток к прямому ребру
                e[a][b].flow += augFlow;
                // соответственно убавить поток от обратного ребра
                e[i][from[i]].flow -= augFlow;
 
                // перейти дальше "назад"
                i = a;
            }
 
            // осталось только добавить наши достижения к счетчикам
            resultFlow += augFlow;
            // стоимость потока взимается за каждую единицу потока!
            resultCost += augFlow * augCost;
        }
 
        //вернуть ответ
        return make_pair(resultFlow, resultCost);
    }
    
 };
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
20.12.2012, 14:04     Графы. Поток минимальной стоимости
Посмотрите здесь:

C++ Поток минимальной стоимости
Графы C++
Нужно создать базу данных (создать пустой бинарный файл). Через поток. Поток бинарного файла описать в виде локальной переменной внутри функции. C++
Скопировать поток и добавить ошибки в поток C++
C++ Скопировать поток в поток
C++ Помогите доделать программу определения минимальной стоимости билета.
C++ Максимальный поток минимальной стоимости
C++ Графы. Найти систему нефтепроводов минимальной суммарной стоимости

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

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

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