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");    }}