[BOJ 14286] 간선 끊어가기 2

문제

---

https://www.acmicpc.net/problem/14286

풀이

---

최대 유량 최소 컷 정리를 사용하는 기본 문제이다.

문제에서 설명하는 최소 컷은 동일 flow network에서 최대 유량과 동일하다.

코드

---

import sys
from collections import deque

n, m = map(int, sys.stdin.readline().split())
graph = [[0] * (n + 1) for _ in range(n + 1)]

for _ in range(m):
    start, end, capacity = map(int, sys.stdin.readline().split())
    graph[start][end] += capacity
    graph[end][start] += capacity

s, t = map(int, sys.stdin.readline().split())

ans = 0
while True:
    prev = [-1] * (n + 1)
    queue = deque([(s, float('inf'))])
    while queue:
        cur, res = queue.popleft()
        
        if graph[cur][t]:
            res = min(res, graph[cur][t])
            prev[t] = cur
            break
        
        for nxt in range(1, n + 1):
            if (prev[nxt] == -1) and graph[cur][nxt]:
                prev[nxt] = cur
                queue.append((nxt, min(res, graph[cur][nxt])))

        if prev[t] != -1:
            break
    
    if prev[t] == -1:
        break

    ans += res
    nxt = t
    while nxt != s:
        cur = prev[nxt]
        graph[cur][nxt] -= res
        graph[nxt][cur] += res
        nxt = cur

print(ans)