匈牙利算法 裸题
//By SiriusRen#include#include #include using namespace std;int n,p[8085],first[8888],next[8888],v[8888],tot,vis[8888],m,xx,yy,ans;void add(int x,int y){v[tot]=y,next[tot]=first[x],first[x]=tot++;}bool dfs(int x){ for(int i=first[x];~i;i=next[i]){ if(!vis[v[i]]){ vis[v[i]]=1; if(!p[v[i]]||dfs(p[v[i]])){ p[v[i]]=x; return 1; } } } return 0;}int main(){ while(~scanf("%d%d",&n,&m)){ memset(p,0,sizeof(p)); memset(first,-1,sizeof(first)),ans=tot=0; for(int i=1;i<=n;i++){ scanf("%d",&xx); while(xx--){ scanf("%d",&yy); add(i,200+yy),add(200+yy,i); } } for(int i=1;i<=n;i++){ if(!p[i]){ memset(vis,0,sizeof(vis)); if(dfs(i))ans++; } } printf("%d\n",ans); }}