아인타, 빈타, 그리고 씬타

문제 링크: https://www.acmicpc.net/problem/32037

 

구사과님의 problem solving에 있는 문제이다. 안타깝게도 나와 구사과님을 제외하고 1명 밖에 안 풀었다.

 

1. Graph construction

 

$S$를 sink, $T$를 source라고 했을 때 다음과 같이 그래프를 만들어보자. 모든 간선의 capacity는 1이다.

 

• 모든 $1 \leq i \leq n$에 대해 $S \rightarrow (i, 0)$
• 모든 $1 \leq i \leq n$에 대해서 $(i, 0) \rightarrow (A[i], 1)$, $(i, 0) \rightarrow (B[i], 1)$
• 모든 $1 \leq i \leq 10000$에 대해서 $(i, 1) \rightarrow (i, 2)$
• 모든 $1 \leq i \leq n$에 대해서 $(C[i], 2) \rightarrow (i, 3)$, $(A[i], 2) \rightarrow (i, 3)$
• 모든 $1 \leq i \leq n$에 대해서 $(i, 3) \rightarrow T$

기존의 $B$와 원소의 교체가 이루어진 $B$을 구분하기 위해 최종적인 $B$와 $C$를 $B'$, $C'$이라고 부르자.

이 그래프의 최대 유량은 $B'$와 $C'$의 교집합의 최대 크기를 의미한다. 이때 교집합은 모든 선택된 $(i, 1) \rightarrow (i, 2)$ 간선들이다.

 

2. 해 구하기

 

$B'$과 $C'$의 교집합의 크기가 최대인 경우는 1에서 구했다. 이제 $B'$와 $C'$의 교집합의 크기를 유지하면서 교집합에 없는 원소들을 제거하는 시행들에 대해서 알아보자.

 

일반성을 잃지 않고 $B'[i]$가 $B' \cap C'$에 없다고 하자.

1. $B'[i]=A[i]$인 경우에는 $C'[i]$를 $A[i]$로 교체한다. 이러면 $A[i]$가 $B' \cap C'$에 추가되어 교집합의 크기가 감소하지 않는다.
2. $B'[i]=B[i]$인 경우에는 $B'[i]$를 $A[i]$로 교체한다. $B'[i]$는 $B' \cap C'$에 없던 원소이기 때문에 교집합의 크기가 감소하지 않는다.

위의 시행을 계속 하면 $B'$과 $C'$에 $B'[i]=A[i]$ ($C'[i]=A[i]$)를 만족하는 원소가 늘어난다. 따라서 위의 시행을 더 이상 실행할 수 없게 되는 순간이 오고, 그 때는 $B' \cap C'$에 없는 $B'$ 혹은 $C'$의 원소가 없다는 것을 의미한다.

 

1에서 최대 유량을 구하는 것은 나이브하게 $O(n^2)$에 구할 수 있다. 하지만 내 $O(n^2)$ 코드는 TLE가 났다. Dinic을 쓰면 $O(n^{1.5})$에 구할 수 있다고 한다. 2에서 최종 해를 구하는 것은 $O(n^2)$에 할 수 있다. 상수가 작아서 통과한다.