mincostflow

最小費用流問題を解きます。 冒頭の

import heapq

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

初期化

G=mcf_graph(K)

Kは頂点の数です。

辺の追加

G.add_edge(s,t,f,c)

最大流量f,コストcの辺をsからtへ張ります。

フロー

G.flow(s,t)

sからtへの最小費用流を求めます。 返り値は二次元タプルであり、(最大フロー,最小コスト)という形になります。

辺一覧

G.edges()

Gの辺一覧を出力します。フローを流した後に見るとどの辺にどれだけ流量が流れているかを見ることが出来ます。edgesはリストの形になっていて、リストの各要素はdictの構造を持っています。 そのdictにおいては、from,to,cap,flow,costという要素を持っています。これは、

• from->toという辺を持っている。
• 最大流量capの辺にflowだけ辺が流れている
• 辺のコストはcostである。

となっています。

使用例

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

import heapq
class mcf_graph():
    # (中略)

BIG=10**9
n,k=map(int,input().split())
A=[[int(i) for i in input().split()]for i in range(n)]
g=mcf_graph(2*n+2)
s=2*n
t=2*n+1
g.add_edge(s,t,n*k,BIG)
for i in range(n):
    g.add_edge(s,i,k,0)
    g.add_edge(n+i,t,k,0)
for i in range(n):
    for j in range(n):
        g.add_edge(i,n+j,1,BIG-A[i][j])
result=g.flow(s,t,n*k)
print(n*k*BIG-result[1])
grid=[["." for j in range(n)] for i in range(n)]
edges=g.edges()
for e in edges:
    if e["from"]==s or e["to"]==t or e["flow"]==0:
        continue
    grid[e["from"]][e["to"]-n]="X"
for i in range(n):
    print("".join(grid[i]))