专栏首页mlhduoj-----(1068)Girls and Boys(二分匹配)

hduoj-----(1068)Girls and Boys(二分匹配)

Girls and Boys

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

Problem Description

the second year of the university somebody started a study on the romantic relations between the students. The relation “romantically involved” is defined between one girl and one boy. For the study reasons it is necessary to find out the maximum set satisfying the condition: there are no two students in the set who have been “romantically involved”. The result of the program is the number of students in such a set. The input contains several data sets in text format. Each data set represents one set of subjects of the study, with the following description: the number of students the description of each student, in the following format student_identifier:(number_of_romantic_relations) student_identifier1 student_identifier2 student_identifier3 ... or student_identifier:(0) The student_identifier is an integer number between 0 and n-1, for n subjects. For each given data set, the program should write to standard output a line containing the result.

Sample Input

7 0: (3) 4 5 6 1: (2) 4 6 2: (0) 3: (0) 4: (2) 0 1 5: (1) 0 6: (2) 0 1 3 0: (2) 1 2 1: (1) 0 2: (1) 0

Sample Output

5 2

Source

Southeastern Europe 2000

题意大致为: 有一个学校,男生女生要搭配,然后排除男神和男生搞基,女生和女生玩拉拉的意思,问最少有多少个落单的倒霉求?

其实就是变相的,最大匹配,就是求出了最大匹配,然后剩下的那些个倒霉求就是所求的答案嘛.....

代码:

 1 #include<cstring>
 2 #include<cstdio>
 3 #include<cstdlib>
 4 using namespace std;
 5 const int maxn=1005;
 6 int n,a,b,c;
 7 bool mat[maxn][maxn];
 8 bool vis[maxn];
 9 int girl[maxn];
10 bool check(int x){
11     for(int i=0;i<n;i++){
12         if(mat[x][i]==1&&!vis[i]){
13             vis[i]=1;
14             if(girl[i]==-1||check(girl[i])){
15               girl[i]=x;
16                return 1;
17             }
18         }
19     }
20     return 0;
21 }
22 int main()
23 {
24     //freopen("test.in","r",stdin);
25     while(scanf("%d",&n)!=EOF){
26         memset(mat,0,sizeof(mat));
27         memset(girl,-1,sizeof(girl));
28         for(int i=0;i<n;i++){
29           scanf("%d: (%d)",&a,&b);
30           while(b--){
31               scanf("%d",&c);
32               mat[a][c]=1;
33           }
34         }
35         int ans=0;
36         for(int j=0;j<n;j++){
37             memset(vis,0,sizeof(vis));
38             if(check(j))ans++;
39         }
40     /*通过最大二分匹配,我们得到了最大匹配数,但是由于男生女生
41     都算了一遍,所以是不是就得除以二。这样就是最大匹配数了*/
42         printf("%d\n",n-ans/2);
43     }
44   return 0;
45 }

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • hdu----(1950)Bridging signals(最长递增子序列 (LIS) )

    Bridging signals Time Limit: 5000/1000 MS (Java/Others)    Memory Limit: 65536/3...

    Gxjun
  • HDUOJ-------2493Timer(数学 2008北京现场赛H题)

    Timer Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Jav...

    Gxjun
  • HDUOJ----(1031)Design T-Shirt

    Design T-Shirt Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/327...

    Gxjun
  • 使用 PInvoke.net Visual Studio Extension 辅助编写 Win32 函数签名

    2018-07-21 14:35

    walterlv
  • Codeforces Round #622 (Div. 2) 1313 C1

    C1. Skyscrapers (easy version) time limit per test1 second memory limit per te...

    风骨散人Chiam
  • 搜索专题4 | 旋转棋盘 POJ - 2286

    The rotation game uses a # shaped board, which can hold 24 pieces of square bloc...

    ACM算法日常
  • 欧洲抵押期权的近似封闭公式(QF CF)

    本文的目的是研究使用接近公式近似来定价欧洲抵押贷款期权。 在逻辑持续时间和正常抵押率的假设下,期权到期时的基础价格通过匹配矩近似于移位对数正态分布或规则对数正态...

    栾博舒
  • JDK7并行计算框架介绍一 Fork/Join概述(官方原版-英文)

    New in the Java SE 7 release, the fork/join framework is an implementation of th...

    数据饕餮
  • CodeForces 670C Cinema(排序,离散化)

    C. Cinema time limit per test 2 seconds memory limit per test 256 megabyte...

    ShenduCC
  • P3507 [POI2010]GRA-The Minima Game

    题目描述 Alice and Bob learned the minima game, which they like very much, recently....

    attack

扫码关注云+社区

领取腾讯云代金券