문제 링크
- http://icpc.me/23052
사용 알고리즘
- Matroid Intersection
- Matroid Partition
풀이
Matroid Partition을 이용한 풀이와 Matroid Intersection을 이용한 풀이가 있습니다.
Matroid Partition
그래프 $G=(V, E)$의 간선 집합 $E$에 대해, $E$의 부분집합족 $\mathcal{I}$를 포레스트를 이루는 $F \subset E$들의 집합으로 정의합시다. 문제는 주어진 간선 집합 $E$를 $I_1\cap I_2=\emptyset, I_1\cup I_2=E$를 만족하도록 두 부분 집합 $I_1, I_2 \subset I$로 나눌 수 있는지 판별하는 문제로 바뀌게 됩니다.
이는 간선 집합 $E$를 매트로이드 $\mathcal{M}=(E, \mathcal{I})$의 독립 집합들로 분할하는 문제이므로 Matroid Partition 라이브러리를 이용해 해결할 수 있습니다.
Matroid Intersection
또 다른 매트로이드 $\mathcal{M}’=(E, \mathcal{I}’)$를 정의합시다. 이때 $\mathcal{I}’$는 $E\setminus F$가 연결 그래프인 $F\subset E$들의 집합입니다.
$I \in \mathcal{I} \cap \mathcal{I}’$를 만족하는 가장 큰 $I$, 즉 두 매트로이드 $\mathcal{M} = (E, \mathcal{I}), \mathcal{M}’ = (E, \mathcal{I}’)$의 최대 공통 독립 집합 $I$의 크기가 $N-1$이라면 $2\times (N-1)$개의 간선을 2개의 트리로 분할할 수 있습니다.
따라서 정답을 $O(N^3 \log N)$ 정도에 구할 수 있습니다. 이때 log는 Union-Find에서 붙게 됩니다.
하지만 $\tilde{O}(N^3)$으로는 제한 시간 안에 문제를 해결할 수 없습니다. 그래프의 성질을 이용해서 augmenting path를 빠르게 찾아야 하는데, 이 부분은 대회 공식 해설을 참고하시기 바랍니다.