HDU OJ 1083 Courses 【二分图匹配之最大匹配】
原题连接：点击打开链接
题意：有p门的课，每门课都有若干学生，现在要为每个课程分配一名课代表，每个学生只能担任一门课的课代表，如果每个课都能找到课代表，则输出"YES"，否则"NO"。
思路：入门的二分图最大匹配问题，求的最大匹配数ans 若 ans = p 则输出 YES，否则 NO。
代码：
#include<cstdio>#include<cstring>#include<queue>#include<vector>#include<iostream>#include<algorithm>using namespace std;vector<int>V[1000];int link[1000],use[1000];void init(int n){ int i; for(i=0;i<=n;i++) V[i].clear();}bool Dfs(int v){ int i,j,k; for(i=0;i<V[v].size();i++) { k=V[v][i]; if(!use[k]) { use[k]=1; if(!link[k]||Dfs(link[k])) { link[k]=v; return true; } } } return false;}int MaxMatch(int n){ int i,j,ans=0; memset(link,0,sizeof(link)); for(i=1;i<=n;i++) { memset(use,0,sizeof(use)); if(Dfs(i)) ans++; } return ans;}int main(){ int i,j,n,m,k,t; scanf("%d",&t); while(t--) { int x,y; scanf("%d%d",&n,&m); init(n); for(i=1;i<=n;i++) { scanf("%d",&x); while(x--) { scanf("%d",&y); V[i].push_back(y); } } int ans=MaxMatch(n); if(ans==n) puts("YES"); else puts("NO"); }}