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