147
правок
Изменения
→Реализация
===Реализация===
Пусть есть задана структура <tex>Edge</tex> с следующими полями:
'''struct''' edge:
'''int''' from
'''int''' to
'''double''' c <font color=green>// пропускная способность ребра</font> '''double''' flow <font color=green>// поток через ребро</font> '''double''' price <font color=green>// стоимость перемещения единицы потока через ребро</font>
Будем использовать структуру для хранения ребер графа G. '''Edge[]''' findMinCostMaxFlow(<tex>G: (V, E)</tex>, '''int''' s, '''int''' t):
'''for''' edge '''in''' <tex>E</tex>:
edge.flow = 0
P = путь <tex>s \leadsto t</tex> с наименьшей стоимостью.
maxFlow = <tex>\displaystyle \min_{edge \in P} edge.c - edge.flow</tex>
'''for''' edge '''in''' pathP:
edge.flow += maxFlow
'''return''' flow<tex>E</tex>
===Асимптотика===
