CERC 2011. Racing Car Trail
https://www.acmicpc.net/problem/3419격자 그래프가 주어질 때, 갔던 정점을 다시 들리지 않는 조건으로 First와 Second가 번갈아 움직인다. 움직일 수 없는 사람이 질 때, 각각의 정점을 시작점으로 했을 때, 각각의 정점에서 누가 이기는지를 출력하면 된다.격자 그래프는 이분 그래프다. 정점을 두 집합으로 쪼개서, 현재 정점이 속한 집합을 A, 반대 집합을 B라고 하자. 이 문제의 답은 이분 그래프의 최대 매칭과 관련이 있다.설명을 돕기 위해, 먼저 매칭 크기 == |A| 인 경우를 생각해 보자. 이 때는 First가 A에서 매칭된 B의 정점으로만 움직여주면, 항상 이길 수 있다. B가 어떻게 움직이든간에, A 집합에 있는 정점으로 다시 가게 될 것이고, 그 정점은 매칭에..
공부/Problem solving
2016. 11. 16. 20:28
공지사항
최근에 올라온 글
- Total
- Today
- Yesterday