最大流問題

問題

$N$ 個のタンクと $M$ 本のパイプがあります。

$j$ 本目のパイプはタンク $A_j$ からタンク $B_j$ の方向に毎秒 $C_j$ リットルまでの水を流すことができます。

タンク $1$ からタンク $N$ まで毎秒最大何リットルの水を流すことができますか。

ただし、タンクに水をためることはできません。

[制約]
🔹$ 2 \leqq N \leqq 400 $
🔹$ 1 \leqq M \leqq 4000 $
🔹$ 0 \leqq C_j \leqq 5000 $
🔹$ 答えは5000以下の整数 $

解き方

この問題は最大流問題と呼ばれる、グラフ上の最大流量を求める問題の一種です。

まず、各タンクを頂点とし、各パイプを辺とするグラフを作成します。

辺の容量はそのパイプが運べる最大の水の量 $C_j$ とします。

このグラフに対して、最大流量を求めるアルゴリズムを実行することで、タンク $1$ からタンク $N$ への最大流量を求めることができます。

有名な最大流アルゴリズムには、Ford-Fulkerson アルゴリズムや、Dinic アルゴリズムがあります。

ソースコード

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#--------- 入力例１ ----------
N = 6
M = 7
A = [1, 1, 2, 2, 3, 4, 5]
B = [2, 4, 3, 5, 6, 5, 6]
C = [5, 4, 4, 7, 3, 3, 5]
#-----------------------------

from collections import defaultdict

class FordFulkerson:
    def __init__(self, n):
        self.n = n
        self.graph = defaultdict(list)
        self.visited = [False] * n
    
    def add_edge(self, u, v, c):
        self.graph[u].append([v, c, len(self.graph[v])])
        self.graph[v].append([u, 0, len(self.graph[u]) - 1])
    
    def dfs(self, v, t, f):
        if v == t:
            return f
        self.visited[v] = True
        for i, (nv, cap, rev) in enumerate(self.graph[v]):
            if self.visited[nv] or cap == 0:
                continue
            d = self.dfs(nv, t, min(f, cap))
            if d == 0:
                continue
            self.graph[v][i][1] -= d
            self.graph[nv][rev][1] += d
            return d
        return 0
    
    def max_flow(self, s, t):
        flow = 0
        while True:
            self.visited = [False] * self.n
            f = self.dfs(s, t, float('inf'))
            if f == 0:
                break
            flow += f
        return flow

max_flow = FordFulkerson(N + 1)
for i in range(M):
    max_flow.add_edge(A[i], B[i], C[i])

print(max_flow.max_flow(1, N))

このソースコードは、最大フロー問題を解くためにフォード・ファルカーソン法を実装したものです。

フォード・ファルカーソン法は、エッジのフロー量を増加させることによって最大フローを求めるアルゴリズムです。

このコードでは、最大フロー問題を解くために、FordFulkersonというクラスを定義しています。

このクラスは、グラフの構造を保持するための変数graphと、最大フローを求めるための関数max_flowを持ちます。

まず、入力例１のデータに従ってグラフを構築します。

このグラフは、defaultdictを用いて辞書形式で表現されており、各頂点にはその頂点に接続するエッジ（辺）の情報が保持されています。

次に、最大フローを求めるために、dfs関数を定義しています。

この関数は、sからtへの最大フローを求めるために、深さ優先探索を実行します。

具体的には、現在の頂点から次の頂点へのパスを探索し、最大フローを更新していきます。

最後に、max_flow関数を呼び出すことで、sからtへの最大フローを求めることができます。

この関数は、whileループを用いて、dfs関数を反復的に呼び出して最大フローを求めます。

[実行結果（入力例１）]

8

入力例１の場合、タンク $1$ からタンク $N$ へ毎秒最大 $8$ リットルの水を流すことができることが分かりました。