Алгоритмы поиска блокирующего потока

Определение:
Блокирующий поток —это поток $f$ в сети $G$, что в данной сети $G$ не существует увеличивающего пути (при этом в сети $G_f$ такой путь может существовать, то есть блокирующий поток не обязательно максимален)

Довольно часто (алгоритм Диница) необходимо находить блокирующий поток в ациклической сети, ниже будут приведены несколько алгоритмов, которые это делают.

Жадный алгоритм

Название говорит само за себя, будем жадно пускать поток вдоль произвольного увеличивающего пути в сети $G$. Данный алгоритм чем то похож на Алгоритм Форда-Фалкерсона, но в отличие от него мы не строим остаточную сеть, а всегда ищем увеличивающие пути в исходной сети $G$.

При пускании потока вдоль любого пути из нашей сети $G$ пропадет хотя бы одно ребро (насыщенное потоком) и при этом новых рёбер появится не может (они появляются в остаточной сети $G_f$, а не в $G$), а значит после не более $E$ итераций $t$ станет не достижимым из $s$, а значит наш поток $f$ - блокирующий. Один путь мы ищем с помощью $dfs$, за $O(E)$, следовательно время работы данного алгоритма - $O(E^2)$.

Удаляющий обход

В жадном алгоритме мы совершали много лишних действий. Будем делать то же самое, но теперь если не получилось найти увеличивающий путь пройди по ребру, то это ребро можно удалить, т.к. на любом пути содержащем это ребро точно будет насыщенное потоком.

Оценим время работы. Когда мы просматриваем ребро мы либо удалим его в дальнейшем, либо будет найден увеличивающий путь содержащий это ребро. Каждое ребро удаляется не более одного раза, следовательно удалений $O(E)$. Как было сказано в жадном алгоритме понадобиться найти O(E) путей, а так как мы ищем простые пути их длинна $O(V)$, следовательно мы просматриваем $O(VE + E) = O(VE)$. Число совершенных действий равно числу просмотренных рёбер, следовательно время работы алгоритма $O(VE)$.

Реализация удаляющего обхода

 1 // ptr[v] - номер первого не удалённого ребра
 2 // dist[v] - расстояние от истока
 3 
 4 int dfs(int v, int min_capacity) { 
 5     if (v == T) {
 6         return min_c;
 7     }
 8     for (int i = ptr[v]; i < (int)g[v].size(); ++i) { 
 9         int u = g[v][i];
10         if (edges[u].get_capacity() == 0) {
11             ++ptr[v]; // ребро отсутствует в остаточной сети, так что удалим его
12             continue;
13         }
14         if (dist[edges[u].v] != dist[v] + 1) {
15             ++ptr[v]; // ребро отсутствует в слоистой сети, так что удалим его
16             continue;
17         }
18         int x = dfs(edges[u].v, min(min_c, edges[u].get_capacity()));
19         if (x) { // нашли увеличивающий путь, по которому можно пустить x потока
20             edges[u].flow += x;
21             edges[u ^ 1].flow -= x;
22             return x;
23         }
24         ++ptr[v]; // перейдя по ребру увеличивающий путь не был найден, так что удалим его
25     }
26     return 0;
27 }
28 
29 void find_blocked_flow() {
30     fill(ptr, ptr + N, 0);
31     while (dfs(S, INF)) {}
32 }

Алгоритм Малхотры — Кумара — Махешвари

напишу потом, все равно его никто и никогда не будет использовать

---

Автор конспекта: Станислав Донской

По всем вопросам пишите в telegram @stasana