题目来源：https://vjudge.net/problem/HDU-1083
题意
存在P门课程，从N个人里选出P个课代表，并且不能选相同的人。问是否可以选出？是输出YES，不能输出NO。
思路
用课程去匹配和课程本身有关系的人，若匹配不到，说明不行。
代码
#include<cstdio>
#include<vector>
#include<map>
#include<stack>
#include<cstring>
#include<algorithm>
using namespace std;
int p,n;
int first[
1000];
int parent[
3100];
struct pp
{
int to,next;
} edge[
30000+
10];
bool vis[
3000+
10];
bool dfs(
int x)
{
for(
int i=first[x]; i!=-
1; i=edge[i].next)
{
int w=edge[i].to;
if(!vis[w])
{
vis[w]=
1;
if(!parent[w]||dfs(parent[w]))
{
parent[w]=x;
vis[w]=
0;
return 1;
}
}
}
return 0;
}
int main()
{
int T;
scanf(
"%d",&T);
while(T--)
{
scanf(
"%d%d",&p,&n);
if(n<p)
{
printf(
"NO\n");
continue;
}
int tot=
0;
for(
int i=
1; i<=p; i++)
{
first[i]=-
1;
int x,y;
scanf(
"%d",&x);
while(x>
0)
{
scanf(
"%d",&y);
edge[tot].to=y;
edge[tot].next=first[i];
first[i]=tot++;
x--;
}
}
int flag=
0;
memset(parent,
0,
sizeof(parent));
memset(vis,
0,
sizeof(vis));
for(
int i=
1; i<=p; i++)
{
if(!dfs(i))
{
flag=
1;
break;
}
}
if(flag)
printf(
"NO\n");
else printf(
"YES\n");
}
}
二维矩阵：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=
500;
int n,p;
int mp[maxn][maxn],vis[maxn],pre[maxn];
int dfs(
int i)
{
for(
int j=
1; j<=n; j++)
{
if(mp[i][j]&&!vis[j])
{
vis[j]=
1;
if(pre[j]==-
1||dfs(pre[j]))
{
vis[j]=
0;
pre[j]=i;
return 1;
}
}
}
return 0;
}
int main()
{
int T;
scanf(
"%d",&T);
while(T--)
{
memset(mp,
0,
sizeof(mp));
scanf(
"%d%d",&p,&n);
for(
int i=
1; i<=p; i++)
{
int num,x;
scanf(
"%d",&num);
while(num--)
{
scanf(
"%d",&x);
mp[i][x]=
1;
}
}
memset(pre,-
1,
sizeof(pre));
memset(vis,
0,
sizeof(vis));
int ret=
0;
for(
int i=
1; i<=p; i++)
ret+=dfs(i);
if(ret==p)
printf(
"YES\n");
else printf(
"NO\n");
}
}
