355
правок
Изменения
Нет описания правки
Запустим в новой сети один из алгоритмов поиска максимального потока. Если он не смог полностью насытить все ребра их истока, то и никакой другой по величине поток этого сделать не сможет, значит, циркуляции нет. Для получения величин потоков по каждому ребру изначальной сети в случае, если циркуляция есть, достаточно просто прибавить к потокам в ребрах $e'_i$ величины $l_i$.
</wikitex>
==Псевдокод==
G // пустой граф, вершины 0 и n + 1 - исток и сток
n, m; // вершин, ребер в исходном графе
edge // ребро с полями (from, to, min_cap, cap)
Для i = 1 to m делай
считать ребро edge
добавить в граф G ребро (0, edge.to, 0, edge.min_cap)
добавить в граф G ребро (edge.from, edge.to, 0, edge.cap - edge.min_cap)
добавить в граф G ребро (edge.from, n + 1, 0, edge.min_cap)
max_flow = наибольший поток в графе G
Для всех ребер, инцидентных истоку, делай
если для текущего ребра flow < cap
циркуляции НЕТ
==Источники==
* [http://e-maxx.ru/algo/flow_with_limits e-maxx]
* [http://dl.dropbox.com/u/39566886/Graph-Theory-Algorithms-M-Ashraf-Iqbal.pdf M. Ashraf Iqbal {{---}}'''Graph Theory and Algorithms''']
