最大流

対象のグラフ（ネットワーク）

有向グラフ

有向枝（アークとも呼ばれる）に容量が設定

有向枝に沿って，容量を上限とした量まで何かを流すことができる．

最大流問題

始点sから終点tまで最大でどれだけ何かを流すことができるか？

始点sと終点t以外の点（中継点）では，流入量＝流出量（その点で外に漏れたり，外から補給したりしない）

2. Ford-Fulkerson法

(1) 概要（詳しくは参考サイト参照）

DFSを使って，始点sから終点tまでのフローを求め続ける方法

一旦確定させたフローを取り消せるように，元の有向枝と逆向きの有向枝（逆辺と呼ばれる）を追加したネットワーク（残余ネットワークと呼ばれる）を考える．

残余ネットワークにおいて，始点sから終点tまでのフローが見つからなくなるまでDFSを実行．

(2) コード例

https://scrapbox.io/files/64099719bfb6d3001b053033.jpg

code:python

# Ford-Fulkersonによる最大流．O(|E|maxflow)

class FordFulkerson:

def __init__(self, N):

self.N = N

self.adj = [[] for i in range(N)]

def add_edge(self, fr, to, cap):

def dfs(self, v, t, flow):

if v == t:

return flow

to, cap, rev_edge, edge_type = cur_edge

d = self.dfs(to, t, min(flow, cap))

if d: # tまで流せたなら

return d

return 0

def maximum_flow(self, s, t):

flow = 0

cur_flow = INF = float('inf')

while cur_flow:

cur_flow = self.dfs(s, t, INF)

flow += cur_flow

return flow

# 現地点での各枝に流れるフロー量の獲得．キー：(始点No，終点No），値：フロー量

def edge_flows(self):

ans = dict()

for v in range(self.N):

if edge_type: # 順方向の枝なら

return ans

N, M = 4, 5

A, B, C = zip(*ABC)

G = FordFulkerson(N) # 引数：点数．0-index

for a, b, c in ABC:

G.add_edge(a - 1, b - 1, c) # 枝の追加．(始点，終点，容量)．0-index

flow_value = G.maximum_flow(0, N - 1) # 始点No.0 -> 終点No.N-1 への流量

print(flow_value)

print(G.edge_flows()) # 各枝を流れる流量．{(0, 1): 2, (0, 2): 2, (1, 2): 1, (1, 3): 1, (2, 3): 3}

練習問題

3. Dinic法

(1) 概要（詳細は参考ページ参照）

$ O(|V|^2|E|)

Ford-Fulkersonでは，DFSの探索途中で終点tまでのフローが見つかったら一旦フローを流して，また最初からDFSを実行する

Dinic法では，さっきのDFSの続きから探索した方がいいんじゃね？という発想

(2) コード例

code: python

# Dinic法による最大流．O(|V|^2|E|)

from collections import deque

class Dinic:

def __init__(self, N):

self.N = N

self.adj = [[] for i in range(N)]

self.depth = None

self.progress = None

def add_edge(self, fr, to, cap):

def bfs(self, s):

while q:

v = q.popleft()

q.append(to)

self.depth = depth

def dfs(self, v, t, flow):

if v == t:

return flow

d = self.dfs(to, t, min(flow, cap))

if d: # tまで流せたなら

return d

return 0

def maximum_flow(self, s, t):

flow = 0

INF = float('inf')

while True:

self.bfs(s)

return flow

cur_flow = self.dfs(s, t, INF)

while cur_flow > 0:

flow += cur_flow

cur_flow = self.dfs(s, t, INF)

# 現地点での各枝に流れるフロー量の獲得．キー：(始点No，終点No），値：フロー量

def edge_flows(self):

ans = dict()

for v in range(self.N):

if edge_type: # 順方向の枝なら

return ans

N, M = 4, 5

A, B, C = zip(*ABC)

G = Dinic(N) # 引数：点数．0-index

for a, b, c in ABC:

G.add_edge(a - 1, b - 1, c) # 枝の追加．(始点，終点，容量)．0-index

flow_value = G.maximum_flow(0, N - 1) # 始点No.0 -> 終点No.N-1 への流量

print(flow_value)

print(G.edge_flows()) # 各枝を流れる流量．{(0, 1): 2, (0, 2): 2, (1, 2): 1, (1, 3): 1, (2, 3): 3}　　

4. NetworkXモジュールを使う方法

code: python

# Networkx使用（Python3.8．PyPy3不可）

import networkx as nx

N, M = 4, 5

G = nx.DiGraph() # 有向グラフの作成

G.add_nodes_from(range(N)) # N個の点を追加．0-index

for a, b, c in ABC:

G.add_edge(a - 1, b - 1, capacity=c) # 枝の追加．0-index

# print(graph)

flow_value, flow_dict = nx.maximum_flow(G, 0, N - 1) # 点0 -> 点N-1

print(flow_value)

print(flow_dict) # {0: {1: 2, 2: 2}, 1: {2: 1, 3: 1}, 2: {3: 3}, 3: {}}

5. Scipyモジュールを使う方法

Scipyではグラフをいくつかの形式で扱える．次の例では，csr_matrix形式．

code: python

# SciPy使用（Python3.8．PyPy3不可）

from scipy.sparse import csr_matrix

from scipy.sparse.csgraph import maximum_flow

N, M = 4, 5

A, B, C = zip(*ABC)

G = csr_matrix((C, (A, B)), shape=(N + 1, N + 1)) # 1-index対応するため +1

# print(G)

print(res.flow_value)

print(res.residual) # csr_matrix形式

# (1, 3) 2

# (2, 1) -2

# (2, 3) 1

# (2, 4) 1

# (3, 1) -2

# (3, 2) -1

# (3, 4) 3

# (4, 2) -1

# (4, 3) -3