跪等大佬相救..
by zwjdd @ 2018-10-06 11:13:38
#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;
}
by yjc_yjc @ 2018-10-06 11:14:38
@[zwjdd](/space/show?uid=44966) 不用谢
by yjc_yjc @ 2018-10-06 11:14:48
@[yjc_yjc](/space/show?uid=81451) 第二个点还是wa啊....
by zwjdd @ 2018-10-06 11:19:13