网络流的搜索比普通搜索的代码就多了一步改变边容量
from collections import deque
n, m, S, T = map(int, input().split()); S, T = S - 1, T - 1
cap = [[0] * n for _ in range(n)]
for _ in range(m):
u, v, c = map(int, input().split())
cap[u - 1][v - 1] += c
e = [[] for _ in range(n)]
for i in range(n):
for j in range(i + 1, n):
if cap[i][j] > 0 or cap[j][i] > 0:
e[i].append(j)
e[j].append(i)
def bfs():
q = deque([[S, 10000]])
vis, pre = [0] * n, [-1] * n; vis[S] = 1
flow = 0
while q:
u, f = q.popleft()
if u == T: flow = f; break
for v in e[u]:
if not vis[v] and cap[u][v] > 0:
q.append([v, min(f, cap[u][v])])
pre[v] = u
vis[v] = 1
cur = T
while pre[cur] != -1:
u, v = pre[cur], cur
cap[u][v] -= flow
cap[v][u] += flow
cur = pre[cur]
return flow
ans = 0
while True:
f = bfs()
if not f: break
ans += f
print(ans)
