[BOJ 5651] 완전 중요한 간선

문제

---

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

풀이

---

완전 중요한 간선을 판별하는 법만 생각해 내면 구현은 어렵지 않은 편이다.

어떤 간선 (a, b)가 완전 중요한 간선이려면, 마지막 상태의 flow network에서 (a, b)에 흐르는 flow와 capacity가 동일해야 한다.

이는 graph 배열에서 확인할 수 있다.

그리고 다음과 같은 명제를 증명할 것이다.

간선 (a, b)는 완전 중요한 간선이 아니다. $ \Leftrightarrow $ a에서 b로 flow 1을 보낼 경로가 존재한다.

(a, b)의 capacity를 1 줄였음에도 불구하고 total flow가 그대로라면 ((a, b)가 완전 중요한 간선이 아니라면), a에서 sink까지 가는 (a, b)를 포함하지 않는 경로가 존재한다.

이때 b부터 sink까지 가는 경로의 flow를 따로 감소시키지 않았으므로, b부터 sink까지 최소 1의 flow가 흐르고 있고, 이는 sink부터 b까지 최소 1의 flow를 흘려보낼 수 있음을 의미한다.

그러므로 a부터 b까지 flow 1을 보낼 수 있다.

반대로, a에서 b로 flow 1을 보낼 경로가 존재한다고 가정하자.

그러면 a $ \rightarrow … \rightarrow $ b $ \rightarrow … \rightarrow $ sink 경로로, 우회해서 flow 1을 보내주면 total flow 또한 변함이 없다.

따라서 위 명제는 참이다.

이를 기반으로 a에서 b로 가는 다른 경로를 찾아보고, 없다면 정답을 1 늘려주면 된다.

코드

---

import sys
from collections import deque

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

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

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

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

        ans += res
        nxt = -1
        while True:
            cur = prev[nxt]
            graph[cur][nxt] -= res
            graph[nxt][cur] += res
            nxt = cur
            if nxt == 1:
                break

    sol = 0
    for a, b in edge:
        if graph[a][b] == 0:
            prev = [-1] * (n + 1)
            queue = deque([a])
            while queue:
                cur = queue.popleft()
                
                for nxt in range(1, n + 1):
                    if (cur == a) and (nxt == b):
                        continue

                    if (nxt == b) and graph[cur][b]:
                        prev[b] = cur
                        break

                    if (prev[nxt] == -1) and graph[cur][nxt]:
                        prev[nxt] = cur
                        queue.append(nxt)

                if prev[b] != -1:
                    break
            
            if prev[b] == -1:
                sol += 1
    
    print(sol)