1# from titan_pylib.graph.flow.max_flow_ford_fulkerson import MaxFlowFordFulkerson
2import sys
3
4
5class MaxFlowFordFulkerson:
6
7 def __init__(self, n: int):
8 self.n: int = n
9 self.m: int = 0
10 self.G: list[list[list[int]]] = [[] for _ in range(n)]
11
12 def add_edge(self, u: int, v: int, w: int) -> None:
13 assert (
14 0 <= u < self.n
15 ), f"Indexerror: {self.__class__.__name__}.add_edge({u}, {v})"
16 assert (
17 0 <= v < self.n
18 ), f"Indexerror: {self.__class__.__name__}.add_edge({u}, {v})"
19 G_u = len(self.G[u])
20 G_v = len(self.G[v])
21 self.G[u].append([v, w, G_v])
22 self.G[v].append([u, 0, G_u])
23 self.m += 2
24
25 def _dfs(self, v: int, g: int, f: int, used: list[int]) -> int:
26 if v == g:
27 return f
28 used[v] = 1
29 for i, (x, w, l) in enumerate(self.G[v]):
30 if used[x]:
31 continue
32 if w == 0:
33 continue
34 fv = self._dfs(x, g, min(f, w), used)
35 if fv > 0:
36 self.G[v][i][1] -= fv
37 self.G[x][l][1] += fv
38 return fv
39 return 0
40
41 def max_flow(self, s: int, g: int, INF: int = 10**18) -> int:
42 """:math:`O(F|E|)"""
43 assert (
44 0 <= s < self.n
45 ), f"Indexerror: {self.__class__.__class__}.max_flow(), {s=}"
46 assert (
47 0 <= g < self.n
48 ), f"Indexerror: {self.__class__.__class__}.max_flow(), {g=}"
49 lim_rec = sys.getrecursionlimit()
50 if lim_rec < self.m:
51 sys.setrecursionlimit(self.m + 1)
52 ans = 0
53 while True:
54 used = [0] * self.n
55 f = self._dfs(s, g, INF, used)
56 if f == 0:
57 break
58 ans += f
59 return ans