import sys
from collections import *
def input(): return map(int,sys.stdin.readline().split())
def BFS():
visited = [-1]*N
dq = deque([(1,0)])
while dq:
now,last = dq.popleft()
if visited[now]<0:
visited[now] = last
if now==2:
return visited
for next in graph[now]:
if graph[now][next]-flow[now][next]:
dq.append((next,now))
def solve():
while visited:=BFS():
now = 2
while now:
last = visited[now]
flow[last][now] += 1; flow[now][last] -= 1
now = last
N,M = input(); N *= 2
graph = [{} for i in range(N)]
for i in range(N//2):
graph[i*2][i*2+1] = 1; graph[i*2+1][i*2] = 0
for _ in range(M):
a,b = input()
graph[a*2-1][b*2-2] = graph[b*2-1][a*2-2] = 1
graph[a*2-2][b*2-1] = graph[b*2-2][a*2-1] = 0
flow = [[0]*N for i in range(N)]
solve()
print(sum(flow[i][2] for i in range(N)))
최대유량 문제이자, 도시 왕복하기 [백준 17412번] 도시 왕복하기 1 (Python3) (tistory.com) 문제의 업그레이드 버전
같은 간선을 중복하면 안되는 도시 왕복하기에서, 같은 정점도 중복하지 않는 조건이 추가되었다.
어떻게 해결할까 고민하다가, 정점을 두 개로 분리하는 아이디어를 생각해냈다.
즉 아이디어를 설명하면(도시 왕복하기 1을 풀었다는 가정하에),
1. N을 2배로 늘려준다. 그리고 i*2, i*2+1 인덱스가 i번 정점을 의미한다.
2. i*2 - i*2+1 사이에 간선을 만들어준다. 다시말해 자기 자신을 한번 더 거치는 간선을 의미한다.
3. 서로 다른 도시의 경우에, i 정점과 j 정점 사이에 간선이 존재하면, i*2+1 - j*2 사이에 간선이 존재하고, j*2+1 - i*2 사이에 간선이 존재한다. (양방향이기 때문)
위와같이 그래프를 만들어주면 자기 자신을 거치는 간선의 용량이 1이기 때문에 모든 정점은 1번밖에 지날 수 없게 된다. 그러면 나머지는 도시 왕복하기 1과 똑같은 방식으로 해결할 수 있다.
간선을 분할해준다는 점에서 길의 개수 [백준 1533번] 길의 개수 (Python3) (tistory.com) 문제와 아이디어가 비슷했던 것 같다. 재미있는 문제였다.
오늘의 교훈) 다양한 최대유량 문제를 해결하자