题意:给你一个p表示测试组数,给你n和m表示课的个数和学生的个数,接下来n行首数字i表示该堂课的学生代表人数,之后为i个学生编码,问能否为每堂课找到一个学生课代表且不冲突;
题解:匈牙利算法模版
另附简单易懂匈牙利算法讲解:
#include#include const int N =305;using namespace std;bool h[N][N];bool vis[N];int link[N];int n,m;bool hungary(int x){ for(int i=1;i<=m;i++){ if(h[x][i]==1&&!vis[i]){ vis[i]=1; if(link[i]==-1||hungary(link[i])){ link[i]=x; return 1; } } } return 0;}int main(){ int t; scanf("%d",&t); while(t--){ scanf("%d %d",&n,&m); memset(h,0,sizeof(h)); memset(link,-1,sizeof(link)); for(int i=1;i<=n;i++){ int u; scanf("%d",&u); while(u--){ int j; scanf("%d",&j); h[i][j]=1; } } int ans=0; for(int i=1;i<=n;i++){ memset(vis,0,sizeof(vis)); if(hungary(i))ans++; } if(ans==n)printf("YES\n"); else printf("NO\n"); } return 0;}