[BOJ 1210] 마피아

문제

---

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

풀이

---

MFMC theorem을 적용할 때 실제로 어떤 엣지를 컷 하는지 알아내는 문제다.

1. 각 톨게이트를 정점 분할하고 그 사이 엣지의 capacity를 점거비로 한다.

2. 고속도로로 연결된 톨게이트 사이를 $ \infty $ capacity의 엣지로 이어준다.

3. 시작점을 source로, 도착점을 sink로 해서 최대 유량을 구한다.

4. 시작점을 기준으로 bfs를 돌린다.

5. 어떤 톨게이트의 정점 분할 내 in 노드엔 도달할 수 있지만 out 노드엔 도달할 수 없다면, 바로 그 톨게이트를 점거해야 하는 것이다.

코드

---

import sys
from collections import deque

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

for i in range(1, n + 1):
    graph[i].append([i + n, cost[i - 1]])

for _ in range(m):
    a, b = map(int, sys.stdin.readline().split())
    graph[a + n].append([b, float('inf')])
    graph[b + n].append([a, float('inf')])

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

        if prev[e + n] != -1:
            break
    
    if prev[e + n] == -1:
        break

    nxt = e + n
    while nxt != s:
        cur = prev[nxt]
        for i in range(len(graph[cur])):
            if graph[cur][i][0] == nxt:
                graph[cur][i][1] -= res
                if graph[cur][i][1] == 0:
                    graph[cur].remove([nxt, 0])
                break
        
        for i in range(len(graph[nxt])):
            if graph[nxt][i][0] == cur:
                graph[nxt][i][1] += res
                break
        else:
            graph[nxt].append([cur, res])
        
        nxt = cur

cut = []
visit = [0] * (2 * n + 1)
visit[s] = 1
queue = deque([s])
while queue:
    cur = queue.popleft()
    
    for nxt, _ in graph[cur]:
        if not visit[nxt]:
            visit[nxt] = 1
            queue.append(nxt)

for i in range(1, n + 1):
    if visit[i] and not visit[i + n]:
        print(i, end=' ')