挺裸的二分匹配!
匈牙利算法:
#include<iostream>
#include<cstring>
#include<cstdlib>
using namespace std;int g[305][90];
int vis[305];
int link[305];
int n,m;int dfs(int u)
{for(int i=1;i<=m;i++)if( !vis[i] && g[u][i] ){vis[i]=1;if( link[i]==-1 || dfs(link[i]) ){link[i]=u;return 1;}}return 0;
}int main()
{
// freopen("in.txt","r",stdin);while(scanf("%d",&n)==1){m=0;memset(g,0,sizeof(g));for(int i=1;i<=n;i++){int a;scanf("%d",&a);for(int j=0;j<a;j++){int x,y;scanf("%d %d",&x,&y);g[i][(x-1)*12+y]=1;if( (x-1)*12+y>m )m=(x-1)*12+y;}}int ans=0;memset(link,-1,sizeof(link));for(int i=1;i<=n;i++){memset(vis,0,sizeof(vis));ans+=dfs(i);}printf("%d\n",ans);}return 0;
}