链接:http://poj.org/problem?id=1469
题意:有P门课,每门课要找一个科代表组成一个委员会,保证每科的课代表不是同一个人,可以组成委员会输出“YES”,否则输出“NO”。
思路:二分图匹配的裸题,匈牙利算法。
资料:http://blog.csdn.net/q3498233/article/details/5786225
代码:
#include <iostream> #include <cstdio> #include <cstring> #include <cctype> #include <cstdlib> #include <cmath> #include <map> #include <set> #include <queue> #include <stack> #include <vector> #include <ctype.h> #include <algorithm> #include <string>r #define PI acos(-1.0) #define mem(a,b) memset(a,b,sizeof(a)) #define maxn 500 #define maxm 30005 using namespace std; int head[maxn]; int t_c,t_s; struct Edge { int v,w; int next; }edge[maxm]; int top=0; int add_edge(int u,int v) { edge[top].v=v; edge[top].next=head[u]; head[u]=top++; return 0; } int from[maxn],tt; bool use[maxn]; bool match(int x) { for(int i=head[x];i!=-1;i=edge[i].next) { int v=edge[i].v; if(!use[v]) { use[v]=1; if(from[v]==-1||match(from[v])) { from[v]=x; return true; } } } return false; } int hungary() { tt=0; mem(from,-1); for(int i=1;i<=t_c;i++) { mem(use,0); if(match(i)) tt++; } return tt; } int init() { mem(head,-1); top=0; return 0; } int main() { int tot; scanf("%d",&tot); while(tot--) { init(); scanf("%d%d",&t_c,&t_s); for(int ii=1;ii<=t_c;ii++) { int t; scanf("%d",&t); for(int i=0;i<t;i++) { int to; scanf("%d",&to); add_edge(ii,to+t_c); } } int res=hungary(); if(res==t_c) printf("YES\n"); else printf("NO\n"); } return 0; }
poj 1469 COURSES 二分图匹配,布布扣,bubuko.com
原文:http://blog.csdn.net/ooooooooe/article/details/22692557