最大流について
問題
s => t に最大量のデータを流す場合、最大どれだけのデータを送信できるか。
class MaxTraffic(object): def __init__(self, N=5): self.N = N self.edge = [[] for i in range(N)] self.used = [0 for i in range(N)] self.inf = 10 ** 9 def append(self, _from, _to, cost): self.edge[_from].append( { 'to': _to, 'cap': cost, 'rev': len(self.edge[_to]), } ) self.edge[_to].append( { 'to': _from, 'cap': 0, 'rev': len(self.edge[_from]) - 1, } ) def dfs(self, v, t, f): """ 増加パスをDFSで探す """ if v == t: return f self.used[v] = 1 for i in range(len(self.edge[v])): e = self.edge[v][i] if not self.used[e['to']] and e['cap'] > 0: d = self.dfs(e['to'], t, min(f, e['cap'])) if d > 0: e['cap'] -= d self.edge[e['to']][e['rev']]['cap'] += d return d return 0 def max_flow(self, s, t): flow = 0 while 1: self.used = [0 for i in range(self.N)] f = self.dfs(s, t, self.inf) if f == 0: return flow flow += f def sample_append(self): self.append(0, 1, 10) self.append(0, 2, 2) self.append(1, 2, 6) self.append(1, 3, 6) self.append(2, 4, 5) self.append(3, 2, 3) self.append(3, 4, 8)
In [166]: m = MaxTraffic() In [166]: m = MaxTraffic() In [167]: m.sample_append() In [167]: m.sample_append() In [168]: m.max_flow(0, 4) In [168]: m.max_flow(0, 4) Out[168]: 11