338
правок
Изменения
Нет описания правки
== Идея ==
== Операция разгрузки (discharged) ==
'''Разгрузка (discharge)''' - операция, которая применяется к переполненной вершине <tex>u</tex>, для того чтобы протолкнуть поток через допустимые ребра в смежные вершины, при необходимости поднимая <tex>u</tex>, делая недопустимые ребра, выходящие из вершины <tex>u</tex>, допустимыми.
Будем хранить для каждой вершины <tex>u</tex> список <tex>N[u]</tex> (список вершин смежных с ней). То есть список содержит каждую вершину <tex>v</tex> такую, что в сети <tex>G = (V, E) ~ (u, v) \in E</tex> или <tex>(v, u) \in E</tex>.
На первую вершину в списке указывает указатель <tex>head[N[u]]</tex>. Для перехода к следующей вершине в списке за <tex>w</tex>, поддерживается указатель <tex>next[w]</tex>. Он равен <tex>null</tex> если <tex>w</tex> - последняя вершина в списке.
Для каждой вершины <tex>u</tex> указатель <tex>current[u]</tex> - указатель на текущую вершину списка. Изначально <tex>current[u] = head[u]</tex>.
'''dischardge'''(u)
'''while''' e[u] > 0
v = current[u]
'''if''' v = null
relabel(u)
current[u] = head[N[u]]
'''else'''
'''if''' c(u, v) > 0 and h[u] = h[v] + 1
push(u, v)
'''else'''
current[u] = next[v]
== Схема алгоритма ==
== Анализ ==
