HDU 1083 Courses(二分图匹配模板)

2021年09月15日 阅读数:4
这篇文章主要向大家介绍HDU 1083 Courses(二分图匹配模板),主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

http://acm.hdu.edu.cn/showproblem.php?pid=1083php

题意:
有p门课和n个学生,每一个学生都选了若干门课,每门课都要找一个同窗来表演,且一个同窗只能表演一门课,判断是否能行。ios

 

思路:
二分图匹配的模板题。ide

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 
 6 int p, n;
 7 int G[305][305];
 8 int vis[305];
 9 int match[305];    //第i学生的选课
10 
11 int dfs(int x)
12 {
13     for (int i = 1; i <= n; i++)
14     {
15         if (G[x][i] && !vis[i])
16         {
17             vis[i] = 1;   //标记,为了为了后面改课时跳过这门课
18             if (!match[i] || dfs(match[i]))   //若是该学生尚未肯定课或者这门课换一个学生
19             {
20                 match[i] = x;
21                 return 1;
22             }
23         }
24     }
25     return 0;
26 }
27 
28 int main()
29 {
30     //freopen("D:\\txt.txt", "r", stdin);
31     int T;
32     int a;
33     cin >> T;
34     while (T--)
35     {
36         memset(match, 0, sizeof(match));
37         memset(G, 0, sizeof(G));
38         cin >> p >> n;
39         int num;
40         for (int i = 1; i <= p; i++)
41         {
42             cin >> num;
43             while (num--)
44             {
45                 cin >> a;
46                 G[i][a] = 1;
47             }
48         }
49         //为每门课匹配学生
50         int i;
51         for (i = 1; i <= p; i++)
52         {
53             memset(vis, 0, sizeof(vis));
54             if (!dfs(i))  break;
55         }
56         if (i == p + 1)   cout << "YES" << endl;
57         else cout << "NO" << endl;
58     }
59 }