[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

'알고리즘 > BOJ' 카테고리의 다른 글

[BOJ] 1023번: 괄호 문자열  (2) 2018.02.11
[BOJ] 1020번: 디지털 카운터  (2) 2018.02.10
[BOJ] 1019번: 책 페이지  (4) 2018.02.07
[BOJ] 1300번: K번째 수  (0) 2018.02.05
[BOJ] 6324번: URLs  (0) 2018.02.01
[BOJ] 1063번: 킹  (0) 2018.01.31
  Comments