这个之前用最大流做过了，用最大流模拟最大匹配。。。建立源汇然后。。
详见 http://blog.csdn.net/zxy_snow/archive/2011/02/06/6173428.aspx
这个是学了匈牙利算法后第一个想起来的题，就来写了下，刚才A掉了，16ms，查了下以前用EK最大流算法A的，300+MS。。时间差好多哎。。
说了，贴代码，水题一道，匈牙利的英文名字 Hungary。
#include <cstdio> #include <cstdlib> #include <iostream> #include <string.h> #include <queue> #include <limits.h> #define MAX 420 using namespace std; int n,m,match; int map[MAX][MAX]; int mat[MAX],used[MAX]; bool Augment(int x) { int i; for(i=1; i<=m+n; i++) if( !used[i] && map[x][i] ) { used[i] = 1; if( mat[i] == 0 || Augment(mat[i]) ) { mat[i] = x; return true; } } return false; } int Hungary() { int i; for(i=1; i<=m+n; i++) { memset(used,0,sizeof(used)); if( Augment(i) ) match++; } return match; } int main() { int i,ans,to,num; while( scanf("%d%d",&n,&m) != EOF ) { memset(map,0,sizeof(map)); memset(mat,0,sizeof(mat)); for(i=1; i<=n; i++) { scanf("%d",&num); while( num-- ) { scanf("%d",&to); map[m+i][to] = 1; } } match = 0; ans = Hungary(); printf("%d/n",ans); } return 0; }
