Я застрял в проблеме Дефектный поток
Я не понимаю, как F [u] = 0 гарантирует ациклический граф в подходе ниже
Я нашел комментарий в редакции Но это не очень понятно
comment -> если нет вершины v, в которой f [v] = 0, то у нас есть цикл в графе, потому что у каждой вершины графа есть хотя бы одно входящее ребро. (Рассмотрим самый длинный простой путь в оставшемся графе, мы знаем, что вершина головы в пути имеет входящее ребро, и голова этого ребра также находится в пути).
Пожалуйста, кто-нибудь объяснит, какова правильная причина вышеупомянутого утверждения?
Ключевым элементом при решении задачи является следующее наблюдение: если мы знаем все входящие ребра вершины, все остальные ребра должны быть исходящими. Источник не имеет входящих ребер, поэтому мы уже знаем, что все его ребра являются исходящими. Для всех остальных вершин, кроме стока, количество входящего и исходящего потока одинаково и равно половине суммы потока вдоль его падающих ребер. Алгоритм состоит в том, чтобы повторно направлять весь поток из вершин, для которых известны все входящие ребра. Это можно сделать с помощью одной BFS:
for all v from 2 to n-1
f[v] := sum(flow(v,u))/2;
put source in queue
while queue is not empty
v := pop(queue)
for all edges (v, u)
if (v, u) is not directed yet
direct v -> u
f[u] = f[u] - flow(v,u)
if u not sink and f[u] = 0
push(queue, u)
Поскольку поток не содержит циклов, мы можем топологически отсортировать вершины. Тогда
мы можем быть уверены, что, пока все направления ребер не известны, мы можем поставить в очередь хотя бы первую вершину с неизвестными ребрами, поскольку все ее входящие ребра будут из вершин с более низкими индексами, но мы взяли первое вершина с неизвестными ребрами.
Время: O (n + m)
Память: O (n + m)
Реализация: c ++