GRL_7の解答例(Python)

2部マッチングに関する問題です．

1. GRL_7_A: Bipartite Matching

# GRL_7_A: Bipartite Matching
# GRL_6_A のVとs,tを変えただけ
# アルゴリズムイントロダクション 27章
from collections import deque

# 最大フローとして解ける
X,Y,E = map(int,input().split())
V = X+Y+2

# 最大フローとして解きたい s=0, t=X+Y+1を追加しておく
s = 0
t = X+Y+1
adjacent_list_residual = [[0]*V for _ in range(V)]
for _ in range(E):
    x,y = map(int,input().split())
    x = x+1 # sを追加したので1つずれる
    y = y+X+1 # sとX分ずれる
    # print(x,y)
    # 残余ネットワーク
    adjacent_list_residual[x][y] = 1 # 平等にマッチングすればいいので容量は1
    adjacent_list_residual[y][x] = 0 # 最初は逆流は0(書かなくてもよいが明示した)
    
    # s to x, y to t
    adjacent_list_residual[s][x] = 1 # 平等にマッチングすればいいので容量は1
    adjacent_list_residual[y][t] = 1 # 平等にマッチングすればいいので容量は1
    
def ford_fulkerson():
    max_flow = 0
    while True:
        # print(adjacent_list_residual)
        parent = find_path()
        if parent == False:
            break
        else:
            # path から最小の容量を見つけ出す
            delta_flow = float("inf")
            # ゴールからスタートまで経路を復元する
            pos = V-1
            start = 0
            while pos != start:
                # print(pos,end=",")
                delta_flow = min(adjacent_list_residual[parent[pos]][pos],delta_flow)
                pos = parent[pos] # 1個前に遡る
                
            # print(0,delta_flow)
                
            # ゴールからスタートまで経路を復元する
            pos = V-1
            start = 0
            
            while pos != start:
                adjacent_list_residual[parent[pos]][pos] -= delta_flow
                adjacent_list_residual[pos][parent[pos]] += delta_flow
                pos = parent[pos] # 1個前に遡る
                
            max_flow += delta_flow
                
    return max_flow
    
# 増加可能経路と増加可能な容量を返す
def find_path():
    # print("================")
    done_set = set([0])
    queue = deque() # (s,t,c)
    
    parent = [-1]*V
    
    for t,c in enumerate(adjacent_list_residual[0]):
        if c > 0:
            queue.append((0,t,c))
            
    delta_flow = float("inf")
    
    while queue:
        s,t,c = queue.popleft()
        
        # print(s,t,c)
        
        if t not in done_set:
            done_set.add(t)
            parent[t] = s
            for t2,c in enumerate(adjacent_list_residual[t]):
                if c > 0:
                    queue.append((t,t2,c))
                    delta_flow = min(delta_flow,c)
    
    # ゴールまでたどり着いていない場合はFalse
    if V-1 not in done_set:
        return False
        
    return parent # ゴールから辿れば経路を復元できる

print(ford_fulkerson())