# 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

``` 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...

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

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

• ### HDUOJ----（1031）Design T-Shirt

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

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

2018-07-21 14:35

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

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

• ### 搜索专题4 | 旋转棋盘 POJ - 2286

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

• ### 欧洲抵押期权的近似封闭公式（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...

• ### P3507 [POI2010]GRA-The Minima Game

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