poj 1469 COURSES (匈牙利算法)

2016-05-26 · 1 min read · 匈牙利算法

poj 1469 题目链接

题意：p个课程，n个学生，给出每个课程对应选取该课程的学生编号，问能否选出p个学生，使得和课程一一对应。

思路：一眼二分图最大匹配。。。需要注意的是。。两个集合可能分别给出。。建图的最大点数是两个集合的最大数目之和。。。因为没注意这个细节RE了一次。。

/* ***********************************************
Author :111qqz
Created Time :2016年05月26日 星期四 23时53分39秒
File Name :code/poj/1469.cpp
************************************************ */

 1#include <cstdio>
 2#include <cstring>
 3#include <iostream>
 4#include <algorithm>
 5#include <vector>
 6#include <queue>
 7#include <set>
 8#include <map>
 9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define fst first
14#define sec second
15#define lson l,m,rt<<1
16#define rson m+1,r,rt<<1|1
17#define ms(a,x) memset(a,x,sizeof(a))
18typedef long long LL;
19#define pi pair < int ,int >
20#define MP make_pair

 1using namespace std;
 2const double eps = 1E-8;
 3const int dx4[4]={1,0,0,-1};
 4const int dy4[4]={0,-1,1,0};
 5const int inf = 0x3f3f3f3f;
 6const int N=30003;
 7int n,p;
 8int head[405];
 9int cnt ;
10int link[405];
11bool vis[405];
12struct Edge
13{
14    int v;
15    int nxt;
16}edge[N];

1void addedge( int u,int v)
2{
3    edge[cnt].v = v;
4    edge[cnt].nxt = head[u];
5    head[u] = cnt;
6    cnt++;
7}

1bool dfs( int u)
2{
3  //  cout<<"u:"<<u<<endl;
4    for ( int i = head[u] ; i!=-1 ; i = edge[i].nxt)
5    {
6	int v = edge[i].v;
7	if (vis[v]) continue;
8	vis[v] = true;

 1	if (link[v]==-1||dfs(link[v]))
 2	{
 3	    link[v] = u;
 4	    return true;
 5	}
 6    }
 7    return false;
 8}
 9int hungary()
10{
11    int res = 0 ;
12    ms(link,-1);

1    for ( int i = 1 ; i <= p ; i++)
2    {
3	ms(vis,false);
4	if (dfs(i))  res++;
5    }

    return res;

 1}
 2int main()
 3{
 4	#ifndef  ONLINE_JUDGE 
 5	freopen("code/in.txt","r",stdin);
 6  #endif
 7	int T;
 8	scanf("%d",&T);
 9	while (T--)
10	{
11	    scanf("%d%d",&p,&n); 
12	    cnt  = 0;
13	    ms(head,-1);
14	    ms(edge,0);
15	    for ( int i = 1 ; i <= p ; i++)
16	    {
17		int x;
18		scanf("%d",&x);
19		while (x--)
20		{
21		    int y;
22		    scanf("%d",&y);
23		    y+=p;
24		    addedge(i,y);
25		}
26	    }
27	    int ans = hungary();

1	    if (ans==p) puts("YES");
2		else puts("NO");
3	}

1  #ifndef ONLINE_JUDGE  
2  fclose(stdin);
3  #endif
4    return 0;
5}