首页 > 代码库 > HDU1083_Courses_课程_C++
HDU1083_Courses_课程_C++
给你们人工翻译一下题目哈，刚好练一下英语
对于一个组中有 N 个学生和 P 种课程。每个学生能够参加0种，1种或者更多的课程。你的任务是找到一种可能的方案使恰好P个学生同时满足下列条件：
? 方案中的每一个学生选择的是不同的课程（前提是那个学生能够参加该课程）
? 方案中每个课程都被参加了
你的程序应该从读入多组测试数据。第一行文件内容是数据的组数。每一组数据后接下列形式：
P N
数量1 学生1 2 学生1 2 …… 学生1 数量1
数量2 学生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
NO
唔！翻译一道题累死人，比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\n");56 else printf("NO\n");57 }58 return 0;59 }
版权所有，转载请联系作者，违者必究
QQ：740929894
HDU1083_Courses_课程_C++