pku 1469 courses
首先建立二分圖,把P門課程作爲X集合,N個人作爲Y集合,對二分圖進行完備匹配判定。方法是用匈牙利算法求出最大匹配,判斷最大匹配數是否爲P即可。
/*
* Problem: pku1469 courses
* Author: Guo Jiabao
* Time: 2009.3.25 21:45
* State: Solved
* Memo: 求完備匹配
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
const int MAXP=101,MAXN=301;
using namespace std;
struct edge
{
edge *next;
int t;
};
edge *V[MAXP];
edge ES[MAXN*MAXP];
int N,P,EC,Match[MAXN],mat;
bool vis[MAXN];
inline void addedge(int a,int b)
{
ES[++EC].next=V[a];
(V[a]=&ES[EC])->t=b;
}
void init()
{
int i,j,C,a;
scanf("%d%d",&P,&N);
EC=-1;
for (i=1;i<=P;i++)
{
scanf("%d",&C);
V[i]=0;
for (j=1;j<=C;j++)
{
scanf("%d",&a);
addedge(i,a);
}
}
memset(Match,0,sizeof(Match));
mat=0;
}
bool path(int i)
{
for (edge *k=V[i];k;k=k->next)
{
int j=k->t;
if (!vis[j])
{
vis[j]=true;
if (Match[j]==0 || path(Match[j]))
{
Match[j]=i;
return true;
}
}
}
return false;
}
void hungary()
{
for (int i=1;i<=P;i++)
{
memset(vis,0,sizeof(vis));
if (path(i))
mat++;
}
if (mat==P)
printf("YESn");
else
printf("NOn");
}
int main()
{
int i,T;
freopen("courses.in","r",stdin);
freopen("courses.out","w",stdout);
scanf("%d",&T);
for (i=1;i<=T;i++)
{
init();
hungary();
}
return 0;
}