SRM 397 - HouseProtection 문제를 풀다가..
Konig's Theorem 이란게 있어서 찾아보니..

bipartite graph 에서..
minimum vertex cover problem <=> maximum matching problem

이라고 하는군..~




여기서 파란 선이 maximum matching 이고 빨간 점이 minimum vertex cover 이다..
둘다 결과가 6이다..

출처: http://wapedia.mobi/en/König's_theorem_(graph_theory)


그러고보니.. GCJ 2009 이 문제도 이 원리를 이용해서 푸는건감..?


'Problem Solving > Algorithm notes' 카테고리의 다른 글

Euler's phi (Totient function)  (0) 2016.08.15
Inversion Count  (0) 2016.01.31
The Tower of Hanoi  (0) 2011.08.28
Gaussian Prime  (0) 2011.04.03
점과 선분과의 거리  (2) 2011.01.22
Modular Multiplicative Inverse  (0) 2010.06.13
Primality Testing (Miller-Rabin)  (0) 2010.03.23
Modular Exponentiation (Big Mod)  (2) 2010.02.19
KMP (Knuth-Morris-Pratt) Algorithm  (0) 2009.11.15
Bell Number  (0) 2009.07.12

to Top