27
правок
Изменения
→Псевдокод
* <tex>\mathtt{from}</tex> {{---}} вершина начала ребра
* <tex>\mathtt{to}</tex> {{---}} вершина конца ребра
* <tex>\mathtt{capminCap}</tex> {{---}} минимальная пропускная способность ребра* <tex>\mathtt{mincapmaxCap}</tex> {{---}} максимальная пропускная способность ребра
'''function''' circulation(<tex>V,E</tex>):
<tex>G'= {</tex> (<tex>V,\cup s\cup t</tex>,t}<tex>\varnothing</tex> ) <font color=green>// создаём новый граф с исходными вершинами и добавлением s и t {{---}} исток и сток</font>
'''for''' <tex>e : e\in E</tex>
<tex>g</tex> = Edge(<tex>s</tex>, <tex>e</tex>.to, <tex>0</tex>, <tex>e</tex>.mincapminCap) <tex>h</tex> = Edge(<tex>e</tex>.from, <tex>e</tex>.to, <tex>0</tex>, <tex>e</tex>.cap maxCap - <tex>e</tex>.mincapminCap) <tex>k</tex> = Edge(<tex>e</tex>.from, <tex>t</tex>, <tex>0</tex>, <tex>e</tex>.minсapminCap) <tex>G' = G' \cup {</tex>(<tex>\varnothing</tex>, <tex>g,\cup h,\cup k}</tex>) maxFlow = getMaxFlow(<tex>G'</tex>) <font color=green>// наибольший поток в графе G'</font>
'''for''' <tex>e : e\in E'</tex> '''and''' <tex>e</tex>.from <tex>=s</tex>
'''if''' <tex>f</tex>(<tex>e</tex>)<tex> < e</tex>.cap maxCap <font color=green>// если для текущего ребра flow < cap</font>
'''return''' false
'''return''' true
