[BOJ] 1014번: 컨닝

https://www.acmicpc.net/problem/1014

1000번부터 차례로 문제를 풀다가 막혀서 꼭 언젠가는 풀어야겠다고 생각했던 문제입니다. bipartite graph에서의 matching이 익숙하지 않아 엄두를 못내다가 결국 풀어냈네요.

서로 컨닝할 수 있는 위치에 놓여있는 사람을 연결한 그래프를 생각해봅시다. 이 때 이 그래프는 bipartite graph이고, 이 bipartite graph 상에서의 maximum matching은 곧 전체 그래프에 대한 minimum cut이므로 edge가 연결되지 않아 컨닝이 불가능함을 알 수 있습니다. 그러므로 maximum matching을 찾으면 됩니다. 이걸 풀면 11014번(https://www.acmicpc.net/problem/11014)도 따라옵니다.

https://github.com/blisstoner/BOJ/blob/master/1014.cpp