MYF

POJ 1469 COURSES

Posted on | In | | Visitors

题目链接

POJ 1469

方法：二分图

题目分析

题目大意

已知$p$门课，$n$个学生，然后给出$p$门课的学生信息，问，是否能找出n个学生使每一个学生负责一门课

解析

二分图的题目。

首先分析一下，二分图的两个集合非常好找，只要把学生当成一个集合，课程当成一个集合，然后去找两个集合之间的最大匹配，如果最大匹配数为课程的总数的话，也就是说所有课程都得到了匹配，那么则为真，否则为假。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <iomanip>
#include <bitset>
#include <cstring>
#include <iostream>
#include <deque>
#include <algorithm>
#define Memset(a,val) memset(a,val,sizeof(a))
#define PI acos(-1)
#define PB push_back
#define MP make_pair
#define rt(n)       (i == n ? '\n' : ' ')
#define hi         printf("Hi----------\n")
#define IN freopen("input.txt","r",stdin);
#define OUT freopen("output.txt","w",stdout);
#define debug(x) cout<<"Debug : ---"<<x<<"---"<<endl;
#pragma comment(checker, "/STACK:1024000000,1024000000")
using namespace std;
typedef pair<int,int> PII;
typedef long long ll;
const int maxn=300+10;
const int mod=1000000007;
const int INF=0x3f3f3f3f;
const double eps=1e-8;
int g[maxn][maxn]={},used[maxn]={},linker[maxn];
int n,p;
int dfs(int u){
    for (int v=1; v<=n; v++)
        if (g[u][v]&&!used[v]) {
            used[v]=1;
            if (linker[v]==-1 ||dfs(linker[v])) {
                linker[v]=u;
                return 1;
            }
        }
    return 0;
}
int hungary(){
    memset(linker,-1,sizeof(linker));
    int rt=0;
    for (int u=1; u<=p; u++) {
        memset(used,0,sizeof(used));
        rt+=dfs(u);
    }
    return rt;
}
int main(){
    int t,tst,pos;
    scanf("%d",&t);
    while (t--) {
        Memset(g, 0);
        scanf("%d%d",&p,&n);
        for (int i=1; i<=p; i++) {
            scanf("%d",&tst);
            for (int j=1; j<=tst; j++) {
                scanf("%d",&pos);
                g[i][pos]=1;
            }
        }
        int sum = hungary();
        if (sum==p)
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}