[BOJ 15892] 사탕 줍는 로봇

문제

---

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

풀이

---

가장 기본적인 최대 유량 문제이다.

문제마다 엣지가 양방향인지 단방향인지 주의해야 할 것 같다.

또 동일 엣지가 중복해서 나올 수 있는 경우도 고려해야 한다.

코드

---

import sys


def dfs(cur, res):
    if cur == n:
        return res
    
    for nxt in range(2, n + 1):
        if graph[cur][nxt] and not visit[nxt]:
            visit[nxt] = 1
            bottleneck = dfs(nxt, min(res, graph[cur][nxt]))
            if bottleneck:
                graph[cur][nxt] -= bottleneck
                graph[nxt][cur] += bottleneck
                return bottleneck
    
    return 0


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

ans = 0
flow = 1
while flow:
    visit = [0] * (n + 1)
    flow = dfs(1, float('inf'))
    ans += flow

print(ans)