문제 링크
- http://icpc.me/3683
문제 출처
- 2008 NWERC C번
사용 알고리즘
- 이분 매칭
풀이
서로 의견이 충돌하는 학생들을 간선으로 이어줍니다.
고양이를 진출시키고 싶은 학생끼리는 절대 의견이 충돌하지 않고, 개를 진출시키고 싶은 학생끼리도 절대 의견이 충돌하지 않습니다.
그러므로 이분 그래프가 만들어지고, 이분 매칭을 이용해 문제를 풀 수 있습니다.
전체 코드
1 |
|
서로 의견이 충돌하는 학생들을 간선으로 이어줍니다.
고양이를 진출시키고 싶은 학생끼리는 절대 의견이 충돌하지 않고, 개를 진출시키고 싶은 학생끼리도 절대 의견이 충돌하지 않습니다.
그러므로 이분 그래프가 만들어지고, 이분 매칭을 이용해 문제를 풀 수 있습니다.
1 |
|