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);
}
}; |
(
