啊就是一道匈牙利裸题,然而谁能想到我因为scanf在这题上wa了n次呢(我真是。。)
#include<cstdio> #include<cstring> #define maxn 205 #define maxm 40005 using namespace std; int num,last[maxn],to[maxm],nxt[maxm],n,m,used[maxn],match[maxn],cnt; int dfs(int x) { for (int i=last[x];i;i=nxt[i]) { if (!used[to[i]]) { used[to[i]]=1; if (!match[to[i]] || dfs(match[to[i]])) { match[to[i]]=x; return 1; } } } return 0; } void add(int x,int y) { to[++num]=y;nxt[num]=last[x];last[x]=num; } int main() { int i,a,x; while (scanf("%d%d",&n,&m)!=EOF) { memset(last,0,sizeof(last)); memset(nxt,0,sizeof(nxt)); memset(to,0,sizeof(to)); memset(match,0,sizeof(match)); cnt=0;num=0; for (i=1;i<=n;i++) { scanf("%d",&a); while (a--) { scanf("%d",&x); add(i,x); } } for (i=1;i<=n;i++) { memset(used,0,sizeof(used)); cnt+=dfs(i); } printf("%d\n",cnt); } return 0; }
原文:https://www.cnblogs.com/lsykk/p/11844245.html