maxflow

最大フロー問題を解きます。 冒頭の

from collections import deque

が無いとエラーになります。

初期化

G=mf_graph(K)

Kはグラフの頂点数です。 初期化した直後は、頂点数Kで辺0のグラフとなります。

辺の追加

G.add_edge(u,v,c)

uからvへ、最大容量c,流量0の辺を追加します。

flow

ans=G.flow(s,t)

sからtへの最大フローを求めます。

edges

for e in G.edges():
    if e["flow"]==0:
         continue
    print(e)

flowを実行した後には、どの辺にどれだけの流量が流れているかを示す値が残ります。

最大フローを求めた後、実際に最大となる状況を構成することが出来ます。

edgesはリストの形になっていて、リストの各要素はdictの構造を持っています。 そのdictにおいては、from,to,cap,flowという要素を持っています。これは、

• from->toという辺を持っている。
• 最大流量capの辺にflowだけ辺が流れている

という意味となっています。

min_cut

最小カットが求められます。

G.min_cut(s)

長さKのlistが返ってきます。

使用例

(https://atcoder.jp/contests/practice2/tasks/practice2_d)

from collections import deque
class mf_graph:
    # (中略)
N,M=map(int,input().split())
S=[list(input()) for i in range(N)]
G=mf_graph(N*M+2)
for i in range(N):
    for j in range(M):
        if S[i][j]=="#":continue
        v=i*M+j
        if (i+j)%2==0:
            G.add_edge(N*M,v,1)
        else:
            G.add_edge(v,N*M+1,1)
for i in range(N):
    for j in range(M):
        if (i+j)%2 or S[i][j]=="#":continue
        v0=i*M+j
        if i>0 and S[i-1][j]==".":
            v1=(i-1)*M+j
            G.add_edge(v0,v1,1)
        if j>0 and S[i][j-1]==".":
            v1=i*M+(j-1)
            G.add_edge(v0,v1,1)
        if i+1<N and S[i+1][j]==".":
            v1=(i+1)*M+j
            G.add_edge(v0,v1,1)
        if j+1<M and S[i][j+1]==".":
            v1=i*M+(j+1)
            G.add_edge(v0,v1,1)

print(G.flow(N*M,N*M+1))

T=[[S[i][j] for j in range(M)] for i in range(N)]
for e in G.edges():
    if e["from"]==N*M or e["to"]==N*M+1 or e["flow"]==0:
        continue
    i0=e["from"]//M
    j0=e["from"]%M
    i1=e["to"]//M
    j1=e["to"]%M
    if i0==i1+1:
        T[i1][j1]="v"
        T[i0][j0]="^"
    elif j0==j1+1:
        T[i1][j1]=">";T[i0][j0]="<"
    elif i0==i1-1:
        T[i0][j0]="v"
        T[i1][j1]="^"
    else:
        T[i0][j0]=">";T[i1][j1]="<"

for i in range(N):
    print("".join(T[i]))

トラブルシューティング

もしREになった場合、原因として再帰上限に引っかかったということが考えられる。そのような場合においては、

import sys
sys.setrecursionlimit(hoge)

といったコードを先頭に加えるとよい。詳しくはここを参照