GRL_6の解答例(Python)

最大フロー，最小費用流に関する問題です．

1. GRL_6_A: Maximum Flow

# GRL_6_A
# アルゴリズムイントロダクション 27章
from collections import deque

V,E = map(int,input().split())

# グラフを隣接リストとして受け取る
adjacent_list_residual = [[0]*V for _ in range(V)]
flow_dict = {}
for _ in range(E):
    s,t,w = map(int,input().split())
    # 残余ネットワーク(増加可能な容量)の設定
    adjacent_list_residual[s][t] = w
    adjacent_list_residual[t][s] = 0 # 最初は逆流は0

# ford-fulkerson法
def ford_fulkerson():
    max_flow = 0
    while True:
        parent = find_path()
        if parent == False:
            break
        else:
            # 増加可能な量 delta_flow を調べる
            delta_flow = float("inf")
            # ゴールからスタートまで経路を復元する
            pos = V-1
            start = 0
            while pos != start:
                # 増やせる量が最小の辺(ボトルネック)が経路全体の増加可能な量
                delta_flow = min(adjacent_list_residual[parent[pos]][pos],delta_flow)
                pos = parent[pos] # 1個前に遡る
                
            # ゴールからスタートまで経路を復元する
            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():
    done_set = set([0]) # 調査済みの点の集合
    queue = deque() # (s,t,c)
    
    parent = [-1]*V # parent[i] = (iの親)
    
    # queueに始点から出る辺を追加する
    for t,c in enumerate(adjacent_list_residual[0]):
        if c > 0:
            queue.append((0,t,c))
    
    # 残余ネットワークに始点から終点までの経路があるかを探索する
    while queue:
        s,t,c = queue.popleft()
        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))
    
    # ゴールまでたどり着いていない場合はFalse(増加可能路がない)
    if V-1 not in done_set:
        return False
        
    return parent # ゴールから辿れば経路を復元できる

print(ford_fulkerson())

2. GRL_6_B: Minimum Cost Flow

# GRL_6_B
import heapq
V,E,F = map(int,input().split())

graph = [[0]*V for _ in range(V)] # 容量
cost = [[0]*V for _ in range(V)]
for _ in range(E):
    s,t,c,d = map(int,input().split())
    graph[s][t] = c
    cost[s][t] = d
    # cost[t][s] = d # ここが違った
    # 逆向きは余計に移動したものを戻す = 操作を取り消す ことなのでコストはマイナス
    cost[t][s] = -d # 逆向きのコストはマイナス

ans = 0
while F > 0:
    # ダイクストラ法で最小費用の増加可能路を求める
    queue = []
    dist = [float("inf")]*V
    dist[0] = 0
    
    parent = [-1]*V
    # 始点からの辺をqueueに追加
    for t in range(V):
        c = graph[0][t]
        if c > 0:
            queue.append((cost[0][t],0,t))
    heapq.heapify(queue)
    
    # ダイクストラ法で探索
    while queue:
        d,s,t = heapq.heappop(queue)
        # print(d,s,t)
        if dist[s]+d < dist[t]:
            parent[t] = s
            dist[t] = dist[s]+d
            for t2 in range(V):
                c = graph[t][t2]
                if c > 0:
                    heapq.heappush(queue,(cost[t][t2],t,t2))
             
    # 増加可能路がない
    if dist[V-1] == float("inf"):
        ans = -1
        break
                    
    d = dist[V-1]
    
    # 経路の増加可能量を調べる
    start = 0
    pos = V-1
    delta_flow = float("inf")
    while pos != start:
        delta_flow = min(graph[parent[pos]][pos],delta_flow)
        pos = parent[pos]
        
    delta_flow = min(F,delta_flow) # 必要量を超えて増やす必要はない
    
    # 残余ネットワークを更新する
    start = 0
    pos = V-1
    while pos != start:
        graph[parent[pos]][pos] -= delta_flow
        graph[pos][parent[pos]] += delta_flow
        pos = parent[pos]
    
    F -= delta_flow # 必要量を更新する
    ans += delta_flow * d # コストを更新する
    
print(ans)