【二分图+简单题】杭电 hdu 1151 Air Raid
?
/* THE PROGRAM IS MADE BY PYY *//*----------------------------------------// Copyright (c) 2011 panyanyany All rights reserved. URL : http://acm.hdu.edu.cn/showproblem.php?pid=1151 Name : 1151 Air Raid Date : Monday, November 7, 2011 Time Stage : half an hour Result: 49233332011-11-07 20:58:18Accepted115115MS316K1557 BC++pyyTest Data :Review :注意是有向图//----------------------------------------*/#include <stdio.h>#include <vector>using std::vector ;#define MAXSIZE 129inttcase, iStreet, iIntersection ;intlink[MAXSIZE], cover[MAXSIZE] ;intmap[MAXSIZE][MAXSIZE] ;vector<int> adj[MAXSIZE] ;int find (int cur){int i, j ;for (i = 1 ; i <= iIntersection ; ++i){if (cover[i] == false && map[cur][i]){cover[i] = true ;if (link[i] == 0 || find (link[i])){link[i] = cur ;return 1 ;}}}return 0 ;}int main (){int i, j ;int s, e ;int sum, sumLink ;while (~scanf ("%d", &tcase)){while (tcase--){scanf ("%d%d", &iIntersection, &iStreet) ;memset (map, 0, sizeof (map)) ;for (i = 1 ; i <= iStreet ; ++i){scanf ("%d%d", &s, &e) ;map[s][e] = 1 ;//map[e][s] = 1 ;若加上这一句，则此图变为无向图}sum = 0 ;memset (link, 0, sizeof (link)) ;for (i = 1 ; i <= iIntersection ; ++i){memset (cover, 0, sizeof (cover)) ;sum += find (i) ;}sumLink = 0 ;for (i = 1 ; i <= iIntersection ; ++i){sumLink += link[i] ? 1 : 0 ;}//由算法的特点可知，若 S, E 两点连通，则 link[S] = 0, link[E] = S ; 因此后面还要减个 sum//当然，直接 iIntersection – sumLink 也是一样滴～～printf ("%d\n", sum + (iIntersection - sumLink - sum)) ;}}return 0 ;}?