목록이분 그래프 (1)
블로그 옮겼습니다
Codeforces Round #383 (Div. 2) E. Arpa’s overnight party and Mehrdad’s silent entering
http://codeforces.com/contest/742/problem/E N쌍의 커플이 있고 이들이 원형 탁자에 앉아 있다. 이 2N 명의 사람들에게 1번음식 또는 2번음식을 주어야 한다. 단 조건이 있다. 1. 커플은 서로 다른 음식을 먹어야한다. 2. 탁자에서 연속된 세 사람이 같은 음식을 먹으면 안된다. 주어진 조건을 만족하는 조합이 있으면 그것을 출력하고 없으면 -1을 출력하는 문제이다. 우선 0번 ~ 2N-1번 사람들에 대해 2i번 사람과 2i+1번 사람을 간선으로 이어보자. 그리고 커플끼리 간선으로 이어보자. 이분 그래프에서 특정 노드에 대해 인접한 노드들은 모두 색이 다르므로 만약 이렇게 했을 때의 그래프가 이분 그래프라면 주어진 두 조건을 만족할 것이다. 그런데 이렇게 하면 무조건 이..
Algorithm/Problem Solving
2017. 7. 26. 13:46