Изменения

Перейти к: навигация, поиск

Алгоритм "поднять-в-начало"

20 байт добавлено, 01:37, 5 января 2016
Операция разгрузки (discharge)
'''Разгрузка''' (англ. ''discharge'') {{---}} операция, применяемая к переполненной вершине <tex>u</tex>, для того чтобы протолкнуть поток через допустимые ребра в смежные вершины, при необходимости поднимая <tex>u</tex>, делая недопустимые ребра, выходящие из вершины <tex>u</tex>, допустимыми.
Будем хранить для каждой вершины <tex>u</tex> список <tex>N[u]</tex> (список вершин, смежных с ней). То есть список <tex>N[u]</tex> содержит каждую вершину <tex>v</tex> такую, что в сети <tex>G = (V, E) ~ </tex> ребро <tex>(u, v) \in E</tex> или <tex>(v, u) \in E</tex>.
На первую вершину в списке указывает указатель <tex>head[N[u]]</tex>. Для перехода к следующей вершине в списке за <tex>w</tex>, поддерживается указатель <tex>next[w]</tex>. Он равен <tex> \varnothing</tex>, если <tex>w</tex> {{---}} последняя вершина в списке.
Анонимный участник

Навигация