【二分图+最大独立集】北大 poj 2771 Guardian of Decency

?

/* THE PROGRAM IS MADE BY PYY *//*----------------------------------------//Copyright (c) 2011 panyanyany All rights reserved.URL   : http://poj.org/problem?id=2771Name  : 2771 Guardian of DecencyDate  : Monday, November 21, 2011Time Stage : one hour and a half Result: 9585300panyanyany2771Accepted524K2391MSC++2084B2011-11-21 21:10:58Test Data :Review :一开始以为是最大匹配，就是可以去的同学两两匹配，然后找最大的匹配……看了人家的代码才知道，原来是求所谓的最大独立集，要匹配会发生感情的同学然后用总数减去这些同学，就是完全不会谈恋爱的同学了，然后再把那些会恋爱的同学两两拆散，加到完全不会恋爱的同学中，就是最大独立集了。感觉这招够毒的……用时花了2千多毫秒，不知道人家7十多的怎么实现的……//----------------------------------------*/#include <stdio.h>#include <string.h>#include <vector>#include <math.h>using std::vector ;#define MAXSIZE508inttcase, n ;intlink[MAXSIZE], cover[MAXSIZE] ;boolmap[MAXSIZE][MAXSIZE] ;struct characteristic {intage ;charsex ;charmusic_style[101] ;charfav_sport[101] ;bool IsCouple (characteristic other){if ((abs (age - other.age) > 40) ||(sex == other.sex) ||(strcmp (music_style, other.music_style)) ||(!strcmp (fav_sport, other.fav_sport)))return false ;elsereturn true ;}};characteristic pupils[MAXSIZE] ;bool find (int cur){int i, j ;for (i = 1 ; i <= n ; ++i){if (cover[i] == false && map[cur][i] == true){cover[i] = true ;if (link[i] == 0 || find (link[i])){link[i] = cur ;return true ;}}}return false ;}int main (){int i, j ;int sum ;while (~scanf ("%d", &tcase)){while (tcase--){scanf ("%d", &n) ;for (i = 1 ; i <= n ; ++i){scanf ("%d %c %s %s", &pupils[i].age, &pupils[i].sex,pupils[i].music_style, pupils[i].fav_sport) ;//printf ("[%d], [%c], [%s], [%s]\n", pupils[i].age, pupils[i].sex,//pupils[i].music_style, pupils[i].fav_sport) ;}memset (map, 0, sizeof (map)) ;for (i = 1 ; i <= n ; ++i){for (j = 1 ; j <= n ; ++j){map[i][j] = pupils[i].IsCouple (pupils[j]) ;//printf ("%d ", map[i][j]) ;}//puts ("") ;}sum = 0 ;memset (link, 0, sizeof (link)) ;for (i = 1 ; i <= n ; ++i){memset (cover, 0, sizeof (cover)) ;sum += find (i) ;}printf ("%d\n", n - sum/2) ;}}return 0 ;}