本文共 1086 字，大约阅读时间需要 3 分钟。
就是判断一下是不是每一个课程都能找到自己的代表人，做一遍最大匹配看看匹配数是否等于p即可
#include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;typedef long long LL;const int maxn = 400;int p,n,bx[maxn],by[maxn],vis[maxn];bool g[maxn][maxn];int dfs(int now) { for(int i = 1;i <= n;i++) if(g[now][i] && !vis[i]) { vis[i] = true; if(!by[i] || dfs(by[i])) { bx[now] = i; by[i] = now; return 1; } } return 0;}void solve() { memset(bx,0,sizeof(bx)); memset(by,0,sizeof(by)); //为每一门课程寻找代表 int ans = 0; for(int i = 1;i <= p;i++) { if(!bx[i]) { memset(vis,0,sizeof(vis)); ans += dfs(i); } } if(ans == p) puts("YES"); else puts("NO");}int main() { int T; scanf("%d",&T); while(T--) { scanf("%d%d",&p,&n); memset(g,0,sizeof(g)); for(int i = 1;i <= p;i++) { int cnt; scanf("%d",&cnt); for(int j = 1;j <= cnt;j++) { int tmp; scanf("%d",&tmp); g[i][tmp] = true; } } solve(); } return 0;}
转载于:https://www.cnblogs.com/rolight/p/3880546.html