티스토리 뷰

공부/Problem solving

Path Cover of DAG

구사과 2016. 1. 3. 13:45

Problem : 사이클이 없는 유향 그래프 G = (V, E)가 주어졌을 때, 모든 정점을 덮는 최소 개수의 Path를 구하라.

Solution : Path에 집착하면 안된다. 간선들로 풀어서 생각하자. Path 상의 간선이 X개면 N - X개의 Path로 커버 가능하니 선택된 간선의 개수를 최대화하면 된다. 간선을 최대화 할 때 제약 조건은 : 각 정점의 indegree에 선택된 간선이 오직 하나, outdegree 오직 하나인 형태로 구성되어야 한다는 것이다.

이제 각 노드를 두개로 쪼개자. 하나는 indegree, 하나는 outdegree를 상징한다. 실제 그래프 상의 간선을 저 안에 잘 박아두면 이분 그래프가 생기니 이제 최대 매칭을 구한다. O(VE).


https://en.wikipedia.org/wiki/Dilworth's_theorem 라는 게 있는데 이 정리와의 직접적인 관련은 아직 잘 모르겠다..

연습 문제 : https://www.acmicpc.net/problem/1671 https://www.acmicpc.net/problem/3295

'공부 > Problem solving' 카테고리의 다른 글

problem solving 2016.01.30  (0) 2016.01.31
Wunder Fund Round 2016 (Div1 + Div2)  (0) 2016.01.30
거울대칭트리 그래프 (BOJ 2430. BOI 2011)  (0) 2016.01.03
some problem solving 2016.01  (0) 2016.01.03
시간이 돈 (Balkan OI 2011)  (0) 2015.12.28
댓글
공지사항
최근에 올라온 글
Total
Today
Yesterday