[BOJ 6086] 최대 유량

문제

---

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

풀이

---

첫 최대 유량 문제이다.

Edmond-Karp 알고리즘은 어차피 나중에 쓸 거니까, 이 문제는 Ford-Fulkerson 알고리즘으로 풀어보았다.

문제를 제대로 안 읽어 여러 번 틀렸다.

• source와 sink는 A, Z로 정해져 있다.

• 노드는 a ~ z, A ~ Z 총 52개 나올 수 있다.

• 파이프는 양방향으로 흐른다.

세 번째 조건 때문에, graph를 초기화할 때 양방향에 모두 capacity를 더해줘야 한다.

코드

---

import sys

graph = [[0] * 52 for _ in range(52)]


def dfs(cur, res):
    if cur == 25:
        return res
    
    for nxt in range(52):
        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


for _ in range(int(sys.stdin.readline())):
    start, end, capacity = sys.stdin.readline().split()
    
    start = ord(start) - 65 - 6 * start.islower()
    end = ord(end) - 65 - 6 * end.islower()
    
    graph[start][end] += int(capacity)
    graph[end][start] += int(capacity)

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

print(ans)