Girls and Boys
Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 3260 Accepted Submission(s): 1405
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
题目大意:给你每个人互相认识的人,然后问最多能找到多少个人都互不认识。其实就是找:最大独立集合!
已知:二分图最大独立集合 = 节点数 - 最大匹配数
代码:
#include <iostream>
#include <stdio.h>
#include <memory.h>
using namespace std;
const int N = 1005;
int pre[N];
bool map[N][N], flag[N];
int n;
int find(int cur) //匈牙利算法
{
int i;
for(i = 0; i < n; i++)
{
if(map[cur][i] && !flag[i])
{
flag[i] = true;
if(pre[i] == -1 || find(pre[i]))
{
pre[i] = cur;
return 1;
}
}
}
return 0;
}
int main()
{
int i, j, r, k, num, sum;
while(scanf("%d", &n) != EOF)
{
memset(map, false, sizeof(map));
memset(pre, -1, sizeof(pre));
for(i = 0; i < n ; i++)
{
scanf("%d: (%d)", &k, &num); //输入格式注意!
for(j = 0; j < num; j++)
{
scanf("%d", &r);
map[k][r] = true; //建表时
}
}
sum = 0;
for(i = 0; i < n; i++)
{
memset(flag, false, sizeof(flag));
sum += find(i);
}
sum /= 2; //二分图具有对称性,最大匹配数 /= 2
//二分图最大独立集合 = 节点数 - 最大匹配数
printf("%d\n", n - sum);
}
return 0;
}
分享到:
相关推荐
B HDU 5093 Battle ships题意给出一个n行m列的图,*代表海域,o代表冰水,#代表冰山,要想在海域中放置船,保证船与船之间不能相互看到,之间
模式识别_hdu_期末复习资料集合_试卷笔记.zip
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
本人准备2020年保研机试时刷的题目(虽然最后机试取消了,...来自某中流985,在HDU和vjudge平台上大概刷了400道。本文件地图(excel表格)包含了绝大部分我刷过的题目,笔记中具有思路、代码、总结和心得。 大佬勿入!
HDU的一题........HDU DP动态规
hdu2101AC代码
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
搜索 dfs 解题代码 hdu1241
Least Common Multiple ...先利用gcd算法求两个数的最大公约数,再考虑最小公倍数=两数乘积/最大公约数,即可求得最小公倍数。 注意:要考虑到输入的输入的n个数中的0,有0的要去掉0求其他数的最小公倍数。 代码:
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
二分图匹配实例代码及整理 1、匈牙利算法 HDU 1150 #include #include #include using namespace std; int m,n,k; int vis[105]; int mpt[105][105]; int use[105]; int hungary(int x) { for(int i=1;i<m;i++)...
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
hdu1290 解题报告 献给杭电五十周年校庆的礼物 (切西瓜问题,即平面分割空间)
hdu 1166线段树代码
ACM HDU题目分类,我自己总结的大概只有十来个吧
自己做的HDU ACM已经AC的题目