2017/08 썸네일형 리스트형 BOJ)10276 Jewelry Exhibition 문제: icpc.me/10276 각 행이나 열에 빛을 발사해서 보석들을 지킬 때 모든 보석들을 지키는 최소한의 빛의 수를 구하는 문제이다. x행 y열의 위치에 존재하는 보석을 x정점과 y정점을 잇는 간선이라고 생각한다면 결국 모든 보석을 지키는건 각 행(정점)들을 몇개 선택하여 모든 간선을 커버하는 문제로 치환되므로 최소 버텍스 커버 문제로 볼 수 있다. 이분 그래프에서의 최소 버텍스 커버 문제는 쾨닉의 정리에 의해 이분 매칭으로 해결할 수 있다. 12345678910111213141516171819202122232425262728293031323334353637383940414243#include #include #include #include using namespace std;int t, n, m,.. 더보기 이전 1 2 3 다음