Алгоритм Форда-Фалкерсона
Немного теории
Утверждение: (Лемма о потоке через разрез)
Для любого $s-t$ разреза $f(S, T) = |f|$
Доказательство:
$f(S, T) \overset{1}{=} f(S, T) + f(S, S) \overset{2}{=} f(S, V) \overset{3}{=} f(s, V) + f(S \setminus \{s\}, V) \overset{4}{=} f(s, V) \overset{5}{=} |f|$
- из-за антисимметричности потока $f(S, S) = 0$
- $f(S, T) + f(S, S) = \sum\limits_{v \in S} \sum\limits_{u \in T} f(v, u) + \sum\limits_{v \in S} \sum\limits_{u \in S} f(v, u) = \sum\limits_{v \in S} \sum\limits_{u \in V} f(v, u) = f(S, V)$
- так же как и 2
- $\forall v \in S\setminus \{s\}, f(v, V) = 0$ - сохранение потока
- определение
Утверждение: (Теорема Форда-Фалкерсона)
Три следующие утверждения эквивалентны:
- Поток $f$ - максимален
- В остаточной сети нет увеличивающего пути
- Существует $s-t$ разрез, что $f(S, T) = c(S, T)$
Доказательство:
- 1 $\Rightarrow$ 2: Если увеличивающий путь есть, то мы можем увеличить поток вдоль него, значит поток $f$ - не максимален, противоречие
- 2 $\Rightarrow$ 3: Разделим вершины на множество достижимых из $s$ и не достижимых (по рёбрам с $c(v, u) > 0$), т.к. увеличивающего пути нет, то $s$ и $t$ лежат в разных множествах, а значит это s-t разрез. При этом для всех его рёбер $f(v, u) = c(v, u)$, а значит $f(S, T) = c(S, T)$
- 3 $\Rightarrow$ 1: для любого $s-t$ разреза $f(S, T) \leq c(S, T)$, а по лемме о потоке через разрез $|f| = f(S, T) \leq c(S, T)$, значит поток f - максимален
В качестве упражнения предложите сведение поиска минимального разреза к поиску максимального потока.
Алгоритм Форда-Фалкерсона
Идея алгоритма в том, что изначально $\forall{v, u}: f(v, u) = 0$ и мы будем итеративно увеличивать его вдоль увеличивающего пути:
- $f(v, u) = 0$, для всех ребер
- Если сток недостижим из истока в остаточной сети(по ребрам с $c_f(v, u) > 0$) алгоритм завершается
- Найти увеличивающий путь в $G_f$ и пустить вдоль него $\underset{(v, u) \in P}{min} c_f(v, u)$ потока
- Перейти к шагу 2
Если алгоритм завершился, то в остаточной сети нет увеличивающего пути, а значит он нашел максимальный поток. В большинстве задач пропускные способности целые, а значит после каждой итерации алгоритма поток увеличивается хотя бы на 1, увеличивающий путь можно искать с помощью $dfs$, следовательно время работы $O(|F|*(V + E))$.
Пример реализации на C++
1 struct Edge {
2 int v; // вершина, куда ведёт ребро
3 int flow; // поток, текущий по ребру
4 int capacity; // пропускная способность ребра
5
6 Edge(int v, int capacity)
7 : v(v), flow(0), capacity(capacity) {}
8
9 int get_capacity() { // пропускная способность ребра в остаточной сети
10 return capacity - flow;
11 }
12 };
13
14 const int INF = (int)(1e9) + 666;
15 const int N = 666;
16 int S, T; // сток и исток
17
18 vector<Edge> edges;
19 vector<int> graph[N]; // в списке смежности храним не рёбра, и индексы в списке рёбер
20 int used[N];
21 int timer = 1; // для быстрого зануления used-а
22
23 // Будем поддерживать список рёбер в таком состоянии, что для i ребра, (i ^ 1) будет обратным
24 void add_edge(int v, int u, int capacity) {
25 graph[v].emplace_back(edges.size()); // номер ребра в списке
26 edges.emplace_back(u, capacity); // прямое ребро
27 graph[u].emplace_back(edges.size()); // номер ребра
28 edges.emplace_back(v, 0); // обратное ребро
29 }
30 int dfs(int v, int min_capacity) {
31 if (v == T) {
32 // нашли увеличивающий путь, вдоль которого можно пустить min_capacity потока
33 return min_capacity;
34 }
35 used[v] = timer;
36 for (int index : graph[v]) {
37 if (edges[index].get_capacity() == 0) {
38 continue; // ребро отсутсвует в остаточной сети
39 }
40 if (used[edges[index].v] == timer) {
41 continue;
42 }
43 int x = dfs(edges[index].v, min(min_capacity, edges[index].get_capacity()));
44 if (x) { // нашли путь по которому можно пустить x потока
45 edges[index].flow += x;
46 edges[index ^ 1].flow -= x;
47 return x;
48 }
49 }
50 // не существует пути из v в T
51 return 0;
52 }
53
54 int main() {
55 int n, m;
56 cin >> n >> m >> S >> T;
57 for (int i = 0; i < m; ++i) {
58 int v, u, capacity;
59 cin >> v >> u >> capacity;
60 add_edge(v, u, capacity);
61 }
62 while (dfs(S, INF)) { // ищем увеличивающий путь
63 ++timer
64 }
65 // увеличивающего пути нет, следовательно максимальный потока найден
66 int result = 0;
67 for (int index : graph[S]) {
68 result += edges[index].flow;
69 }
70 cout << result << endl;
71 return 0;
72 }
Автор конспекта: Станислав Донской
По всем вопросам пишите в telegram @stasana