import sys
input = sys.stdin.readline
from collections import *
def BFS():
dq = deque([0])
level = [0]*K; level[0] = 1
lvadj = [[] for i in range(K)]
while dq:
now = dq.popleft()
for next in adj[now]:
if graph[now][next]:
if not level[next]:
level[next] = level[now]+1
dq.append(next)
if level[next]==level[now]+1:
lvadj[now].append(next)
if level[K-1]:
return lvadj
def DFS(now,f):
if now==K-1:
return f
while lvadj[now]:
next = lvadj[now].pop()
f1 = DFS(next,min(f,graph[now][next]))
if f1:
graph[now][next] -= f1; graph[next][now] += f1
lvadj[now].append(next)
return f1
def solve():
dq = deque([0])
visited = [0]*K
while dq:
now = dq.popleft()
for next in adj[now]:
if graph[now][next] and not visited[next]:
visited[next] = 1
dq.append(next)
for i in range(1,N+1):
if visited[i] and not visited[i+N]:
print(i,end=" ")
N,M = map(int,input().split()); K = N*2+2
graph = [[0]*K for i in range(K)]; adj = [[] for i in range(K)]
s,e = map(int,input().split())
graph[0][s] = graph[e+N][K-1] = 1e12
adj[0].append(s); adj[s].append(0)
adj[e+N].append(K-1); adj[K-1].append(e+N)
for i in range(1,N+1):
graph[i][i+N] = int(input())
adj[i].append(i+N); adj[i+N].append(i)
for _ in range(M):
a,b = map(int,input().split())
graph[a+N][b] = graph[b+N][a] = 1e12
adj[a+N].append(b); adj[b].append(a+N)
adj[b+N].append(a); adj[a].append(b+N)
while lvadj:=BFS():
while DFS(0,1e12):
pass
solve()MFMC + 디닉 알고리즘 응용문제
최대유량 최소컷 정리 문제인데 간선의 개수가 최대 20000개이기 때문에 에드몬드-카프를 사용할 수 없다. 따라서 디닉 알고리즘을 공부해서 해결하였다.
풀이를 설명하면,
1. 각 톨게이트를 i번의 경우 i번과 i+N번으로 분할한다.
2. i-i+N 사이에 톨게이트 비용을 용량으로 갖는 간선을 만든다.
3. source-시작지점, 도착지점-sink, 그리고 고속도로로 이어진 톨게이트끼리 용량 무한대의 간선을 만든다.
4. 디닉 알고리즘으로 최대유량을 구한다.
5. BFS로 시작지점부터 탐색하여, i에는 도착할 수 있는데 i+N에는 도착하지 못하는 톨게이트가 곧 점거해야하는 도시이다.
1~4까지는 쉽게 해결할 수 있었는데, 5번을 출력하는 과정에서 애를 먹었던 문제였다. 처음에는 간선의 용량이 0이 된 도시를 출력해야한다고 생각했는데, 그렇게 되면 중복하여 출력이 발생한다는 것을 알게되었다. 그래서 꼭 필요한 간선을 찾아서 출력해야 했는데, 이 방법을 떠올리기 쉽지 않았다.
오늘의 교훈) 최대유량이 성립할 때를 추적하는 방법을 고민하자