HDU1083_Courses_课程

HDU1083_Courses_课程_C++

　　给你们人工翻译一下题目哈，刚好练一下英语

　　对于一个组中有 N 个学生和 P 种课程。每个学生能够参加0种，1种或者更多的课程。你的任务是找到一种可能的方案使恰好P个学生同时满足下列条件：

　　　　‧ 方案中的每一个学生选择的是不同的课程（前提是那个学生能够参加该课程）

　　　　‧ 方案中每个课程都被参加了

　　你的程序应该从读入多组测试数据。第一行文件内容是数据的组数。每一组数据后接下列形式：

　　　　P N

　　　　数量₁　　学生_{1 2}　　学生_{1 2}　　……　　学生_{1 数量1}

　　　　数量₂　　学生_{2 2}　　学生_{2 2}　　……　　学生_{2 数量2}

　　　　……

　　　　数量_p　　学生_{p 2}　　学生_{p 2}　　……　　学生_{p 数量p}

　　每组数据中第一行两个整数由空格隔开：P（1≤P≤100）-课程数和 N（1≤N≤300）-学生数。接下来P行用一个数列来描述每个课程。从课程1到课程P，每行用来描述该课程。每行课程开头的一个整数 i （0≤数量 i ≤N）是学生能够参加该课程的数量。接下来，一个空格之后，你将会得到 i 个学生能参加该课程，每两个连续的数由一个空格隔开。学生的编号是从1到N的整数。

　　在连续的两组数据间没有空行。输入的数据保证正确。

　　程序的结果是标准的输出。对于每一组数据如果有可能的方案打印单个的一行 “YES” 否则打印 “NO”。在每行之前不需要任何的空格。

　　一份程序的输入和输出样列：

　　　　样列输入：

　　　　2
　　　　3 3
　　　　3 1 2 3
　　　　2 1 2
　　　　1 1
　　　　3 3
　　　　2 1 3
　　　　2 1 3
　　　　1 1
　　　　样列输出：

　　　　YES

　　唔！翻译一道题累死人，比A它还慢，以后怎么打比赛啊……

　　我们来分析一下问题，其实就是P个课程和N个学生进行二分图匹配，可以有学生不上课，但是每个课程有且只有一个学生上

　　直接匈牙利算法（准备写这个算法，但是还没有码，贴个链接他写得蛮好的一看就懂，等我码完了再来换链接）

　　　　http://blog.csdn.net/dark_scope/article/details/8880547

　　下面是代码

 1 #include<algorithm>
 2 #include<iostream>
 3 #include<cstdlib>
 4 #include<cstring>
 5 #include<cstdio>
 6 #include<cmath>
 7 using namespace std;
 8 
 9 const int N=301;
10 int link[N],n,m;
11 bool g[N][N],f[N];
12 bool dfs(int x)
13 {
14     int i;
15     for (i=1;i<=m;i++)
16         if (f[i]&&g[x][i])
17             {
18                 f[i]=0;
19                 if (!link[i]||dfs(link[i]))
20                     {
21                         link[i]=x;
22                         return 1;
23                     }
24             }
25     return 0;
26 }
27 int main()
28 {
29     int t,i,j,x;
30     scanf("%d",&t);
31     while (t>0)
32         {
33             t--;
34             scanf("%d%d",&n,&m);
35             for (i=1;i<=m;i++)
36                 {
37                     link[i]=0;
38                     for (j=1;j<=n;j++) g[j][i]=0;
39                 }
40             for (i=1;i<=n;i++)
41                 {
42                     scanf("%d",&j);
43                     while (j>0)
44                         {
45                             j--;
46                             scanf("%d",&x);
47                             g[i][x]=1;
48                         }
49                 }
50             for (i=1;i<=n;i++)
51                 {
52                     for (j=1;j<=m;j++) f[j]=1;
53                     if (!dfs(i)) break;
54                 }
55             if (i>n) printf("YES
");
56             else printf("NO
");
57         }
58     return 0;
59 }

QQ：740929894