【二分图+最大匹配】北大 poj 1274 The Perfect Stall
?
/* THE PROGRAM IS MADE BY PYY *//*----------------------------------------//Copyright (c) 2011 panyanyany All rights reserved.URL : http://poj.org/problem?id=1274Name : 1274 The Perfect StallDate : Tuesday, December 20, 2011Time Stage : half an hourResult: 9673709panyanyany1274Accepted324K0MSC++1216B2011-12-20 21:19:16Test Data :Review :水题……//----------------------------------------*/#include <stdio.h>#include <string.h>#define MAXSIZE202intn, m ;intlink[MAXSIZE] ;boolcover[MAXSIZE] ;intgraph[MAXSIZE][MAXSIZE] ;bool find (int cur){int i, j ;for (i = 1 ; i <= graph[cur][0] ; ++i){j = graph[cur][i] ;if (cover[j] == false){cover[j] = true ;if (!link[j] || find (link[j])){link[j] = cur ;return true ;}}}return false ;}int main (void){int i, j ;int sum ;while (~scanf ("%d%d", &n, &m)){for (i = 1 ; i <= n ; ++i){scanf ("%d", &graph[i][0]) ;for (j = 1 ; j <= graph[i][0] ; ++j)scanf ("%d", &graph[i][j]) ;}sum = 0 ;memset (link, 0, sizeof (link)) ;for (i = 1 ; i <= n ; ++i){memset (cover, 0, sizeof (cover)) ;sum += find (i) ;}printf ("%d\n", sum) ;}return 0 ;}?