最大流：残余辺で選択をやり直す

容量つき有向グラフで、始点から終点へ流せる総量を最大化します。逆向きの残余辺が、以前の選択を取り消す仕組みになります。

言語：Python / 計算量：この行列版 Edmonds–Karp は O(V³E) 上界

考え方

各辺に容量と、逆辺を用意。
残余容量が正の始点→終点の経路を探します。
最小残余容量だけ流し、順辺を減らし逆辺を増やします。

具体例

s→a が3、a→t が2なら、その道に流せるのは2。辺の容量を単純に全部足すことはできません。

実装

from collections import deque
cap=[[0,3,1,0],[0,0,0,2],[0,0,0,2],[0,0,0,0]]
flow=0
while True:
    p=[-1]*4;p[0]=0;q=deque([0])
    while q and p[3]<0:
        v=q.popleft()
        for u in range(4):
            if cap[v][u]>0 and p[u]<0:p[u]=v;q.append(u)
    if p[3]<0:break
    f=10**18;u=3
    while u!=0:f=min(f,cap[p[u]][u]);u=p[u]
    u=3
    while u!=0:
        v=p[u];cap[v][u]-=f;cap[u][v]+=f;u=v
    flow+=f
print(flow)

注意する条件

逆辺を忘れると貪欲な経路選択から戻れません。大規模問題はDinicなどを検討。容量行列は O(V²) メモリです。

確認問題

例のネットワークの最大流は？

解答と理由

a経由で2、もう一方で1。合計3を流せます。

実装課題

講義コードの s→a 容量3を1に変えると最大流はいくつか。変更したコードを実行し、理由も確認。入力なし。

出力:
2

参考実装

from collections import deque
cap=[[0,1,1,0],[0,0,0,2],[0,0,0,2],[0,0,0,0]]
ans=0
while True:
    p=[-1]*4;p[0]=0;q=deque([0])
    while q and p[3]<0:
        v=q.popleft()
        for u in range(4):
            if cap[v][u]>0 and p[u]<0:p[u]=v;q.append(u)
    if p[3]<0:break
    f=10**18;u=3
    while u:f=min(f,cap[p[u]][u]);u=p[u]
    u=3
    while u:
        v=p[u];cap[v][u]-=f;cap[u][v]+=f;u=v
    ans+=f
print(ans)

読了の記録・下書き・メモへ