最大流について

問題

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