| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
匈牙利算法 844MS#include <cstdio>
#include <bitset>
#include <cstring>
using namespace std;
int n,p,id;
struct edge
{
int v,nx;
}set[300005];
int head[305],match[305];
bitset<105> chk;
void Addedge(int u,int v)
{
id++;set[id].v=v;set[id].nx=head[u];
head[u]=id;
}
bool dfs(int u)
{
for(int k=head[u];k>0;k=set[k].nx)
if(!chk[set[k].v])
{
chk[set[k].v]=true;
if((match[set[k].v]==0)||dfs(match[set[k].v]))
{
match[set[k].v]=u;return true;
}
}
return false;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("courses.in","r",stdin);
freopen("courses.out","w",stdout);
#endif
int cas=0;scanf("%d",&cas);
while(cas--)
{
id=0;
memset(match,0,sizeof(match));
memset(head,-1,sizeof(head));
int knum,stu;
scanf("%d%d",&p,&n);
for(int i=1;i<=p;i++)
{
scanf("%d",&knum);
for(int j=1;j<=knum;j++)
{
scanf("%d",&stu);
Addedge(stu,i);
}
}
int ans=0;
for(int i=1;i<=n;i++)
{
chk.reset();
if(dfs(i))ans++;
}
if(ans==p)puts("YES");
else puts("NO");
}
fclose(stdin); fclose(stdout);
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator