【二分图+最大匹配】北大 poj 3041 Asteroids
?
/* THE PROGRAM IS MADE BY PYY *//*----------------------------------------//Copyright (c) 2011 panyanyany All rights reserved.URL : http://poj.org/problem?id=3041Name : 3041 AsteroidsDate : Saturday, November 19, 2011Time Stage : one hourResult: 9578655panyanyany3041Accepted224K32MSC++1259B2011-11-19 21:21:019578476panyanyany3041Accepted264K16MSC++1304B2011-11-19 20:46:429578453panyanyany3041Wrong AnswerC++1310B2011-11-19 20:42:34Test Data :Review :一开始觉得是最小顶点覆盖，结果错了，看人家的钥匙报告，才知道原来是最大匹配……囧……//----------------------------------------*/#include <stdio.h>#include <string.h>#include <vector>using std::vector ;#define MAXSIZE508intn, k ;intlink[MAXSIZE], cover[MAXSIZE] ;vector<int> adj[MAXSIZE] ;int find (int cur){int i, j ;for (i = 0 ; i < adj[cur].size () ; ++i){j = adj[cur][i] ;if (cover[j] == false){cover[j] = true ;if (link[j] == false || find (link[j])){link[j] = cur ;return 1 ;}}}return 0 ;}int main (){int i, j ;int r, c ;int sum ;while (~scanf ("%d%d", &n, &k)){for (i = 1 ; i <= n ; ++i)adj[i].clear () ;for (i = 1 ; i <= k ; ++i){scanf ("%d%d", &r, &c) ;adj[r].push_back (c) ;}memset (link, 0, sizeof (link)) ;sum = 0 ;for (i = 1 ; i <= n ; ++i){memset (cover, 0, sizeof (cover)) ;sum += find (i) ;}// 感觉应该是最小顶点覆盖，怎么会是最大匹配呢？printf ("%d\n", sum) ;}return 0 ;}?