题解 P2417 【课程】

这是一道经典的二分图最大匹配的裸题。。。 匈牙利大法好。。。 然而一开始挂了不计 n (n>=10) 次，对拍了半小时，读入优化的锅。。。 有毒。。。 附代码： ```cpp #include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #define MAXN 110 #define MAXM 20010 using namespace std; int t,n,p,ans; int f[MAXM],a[MAXN][MAXM];//匹配数组 与 路径数组 bool vis[MAXM];//是否匹配标记 bool find(int x){//寻找 for(int i=1;i<=n;i++){//枚举所有学生 if(!vis[i]&&a[x][i]){//若有兴趣，且未匹配 vis[i]=true;//标记 if(f[i]==-1||find(f[i])){//若未匹配 或 能腾出一个空位 f[i]=x;//修改 return true; } } } return false; } int main(){ int x,y; scanf("%d",&t); while(t--){ memset(a,0,sizeof(a)); memset(f,-1,sizeof(f)); memset(vis,false,sizeof(vis)); scanf("%d%d",&p,&n);//记住，读入优化有毒。。。 if(p>n){//若 课程数 多于 学生数 ，一定不能全匹配 printf("NO\n"); continue; } for(int i=1;i<=p;i++){//对 每个课程 与 每个学生 建立关系 scanf("%d",&x); for(int j=1;j<=x;j++){ scanf("%d",&y); a[i][y]=1; } } ans=0; for(int i=1;i<=p;i++){ memset(vis,false,sizeof(vis)); if(find(i)) ans++;//匹配计数 } if(ans==p)printf("YES\n"); else printf("NO\n"); } return 0; } ```