专栏首页mlHDU-----(1083)Courses(最大匹配)

HDU-----(1083)Courses(最大匹配)

Courses

Time Limit: 20000/10000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 3767    Accepted Submission(s): 1800

Problem Description

Consider a group of N students and P courses. Each student visits zero, one or more than one courses. Your task is to determine whether it is possible to form a committee of exactly P students that satisfies simultaneously the conditions: . every student in the committee represents a different course (a student can represent a course if he/she visits that course) . each course has a representative in the committee Your program should read sets of data from a text file. The first line of the input file contains the number of the data sets. Each data set is presented in the following format: P N Count1 Student1 1 Student1 2 ... Student1 Count1 Count2 Student2 1 Student2 2 ... Student2 Count2 ...... CountP StudentP 1 StudentP 2 ... StudentP CountP The first line in each data set contains two positive integers separated by one blank: P (1 <= P <= 100) - the number of courses and N (1 <= N <= 300) - the number of students. The next P lines describe in sequence of the courses . from course 1 to course P, each line describing a course. The description of course i is a line that starts with an integer Count i (0 <= Count i <= N) representing the number of students visiting course i. Next, after a blank, you'll find the Count i students, visiting the course, each two consecutive separated by one blank. Students are numbered with the positive integers from 1 to N. There are no blank lines between consecutive sets of data. Input data are correct. The result of the program is on the standard output. For each input data set the program prints on a single line "YES" if it is possible to form a committee and "NO" otherwise. There should not be any leading blanks at the start of the line. An example of program input and output:

Sample Input

2 3 3 3 1 2 3 2 1 2 1 1 3 3 2 1 3 2 1 3 1 1

Sample Output

YES NO

Source

Southeastern Europe 2000

  给定一个课程数目和每一个门课程听课的人的编号,问能否每一门课都有人听课...!

代码:

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<vector>
 4 using namespace std;
 5 const int maxn=301;
 6 vector<int>mat[maxn];
 7 int judge[maxn];
 8 bool vis[maxn];
 9 bool skm(int x){
10   vector<int>::iterator it;
11   for(it=mat[x].begin();it<mat[x].end();it++)
12     {
13       if(!vis[*it])
14       {
15         vis[*it]=1;
16      if(judge[*it]==0||skm(judge[*it]))
17      {
18          judge[*it]=x;
19          return 1;
20      }
21     }
22   }
23   return 0;
24 }
25 
26 int main()
27 {
28     int cas,n,m,t,a,i;
29     scanf("%d",&cas);
30     while(cas--)
31     {
32      scanf("%d%d",&n,&m);
33      memset(judge,0,sizeof(int)*(m+2));
34     for( i=1;i<=n;i++)
35     {
36       mat[i].clear();
37       scanf("%d",&t);
38      while(t--){
39          scanf("%d",&a);
40         mat[i].push_back(a);
41      }
42     }
43     for(i=1;i<=n;i++){
44       memset(vis,0,sizeof(bool)*(m+2));
45       if(!skm(i))break;
46     }
47     if(i>n) printf("YES\n");
48     else printf("NO\n");
49     }
50  return 0;
51 }

采用邻接矩阵做:

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<vector>
 4 #include<cstdlib>
 5 #include<iostream>
 6 using namespace std;
 7 const int maxn=505;
 8 bool mat[maxn][maxn];
 9 int judge[maxn];
10 bool vis[maxn];
11 int n,m;
12 bool skm(int x){
13   for(int i=1;i<=m;i++)
14   {
15       if(!vis[i]&&mat[x][i])
16       {
17         vis[i]=1;
18      if(judge[i]==0||skm(judge[i]))
19      {
20          judge[i]=x;
21          return 1;
22      }
23     }
24   }
25   return 0;
26 }
27 int main()
28 {
29     int cas,t,a,i;
30     //freopen("test.in","r",stdin);
31     scanf("%d",&cas);
32     while(cas--)
33     {
34      scanf("%d%d",&n,&m);
35      memset(judge,0,sizeof(judge));
36      memset(mat,0,sizeof(mat));
37     for( i=1;i<=n;i++)
38     {
39       scanf("%d",&t);
40      while(t--)
41      {
42          scanf("%d",&a);
43          mat[i][a]=1;
44      }
45     }
46     for(i=1;i<=n;i++){
47       memset(vis,0,sizeof(vis));
48       if(!skm(i))break;
49     }
50     if(i>n)
51         printf("YES\n");
52     else
53         printf("NO\n");
54     }
55  return 0;
56 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • HDUOJ----1165Eddy's research II

    Eddy's research II Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536...

    Gxjun
  • poj----(1470)Closest Common Ancestors(LCA)

    Closest Common Ancestors Time Limit: 2000MS Memory Limit: 10000K Total S...

    Gxjun
  • HDUOJ-----2852 KiKi's K-Number(树状数组+二分)

    KiKi's K-Number Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 32768/32...

    Gxjun
  • leetcode-492-Construct the Rectangle

    chenjx85
  • HDUOJ----1165Eddy's research II

    Eddy's research II Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536...

    Gxjun
  • 基于阶段树模型的一类新的生成分类器(AI)

    用于分类的生成模型使用类别变量和特征的联合概率分布来构造决策规则。在生成模型中,贝叶斯网络和朴素贝叶斯分类器是最常用的,并且提供了所有变量之间关系的清晰图形表示...

    田冠宇
  • 人工智能极大提升天文数据处理速度

    引力透镜效应是指空间中一个遥远天体的图像(如星系)被大质量天体的引力扭曲和放大,例如一个星系群在一个较小、遥远天体的前面就会引发这种效应。这种有用的现象能帮助科...

    人工智能快报
  • The Address of an Array

    青木
  • CNCC | 丘成桐演讲全文:工程上取得很大发展,但理论基础仍非常薄弱,人工智能需要一个可被证明的理论作为基础

    AI科技评论消息,2017年10月26日上午,中国计算机学会(CCF)主办的第十四届中国计算机大会(CNCC 2017)正式在福州海峡国际会展中心开幕,雷锋网作...

    AI科技评论
  • 回归树(一)

    线性回归模型需要拟合全部的样本点(局部加权线性回归除外)。当数据拥有众多特征并且特征之间的关系十分复杂时,构建全局模型的想法就不切实际。一种可行的方法是将数据集...

    用户6021899

扫码关注云+社区

领取腾讯云代金券