Girls and Boys
Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 6595 Accepted Submission(s): 2976
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.
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
题意:
给出 N(<= 500)有 N 个同学 ,给出每个同学自己所中意的人,求一个最大集合,这个集合里面的人相互之间没有任何喜欢的关系。
思路:
二分图最大匹配。匈牙利算法。求最大独立集,最大独立集 = 结点数 - 最大匹配数。每个点都匹配一次的话,最终结果要除以2,因为这是无向图。
AC:
#include <cstdio> #include <string.h> using namespace std; int n; int w[505][505],vis[505],linker[505]; bool dfs(int u) { for(int v = 0;v < n;v++) if(w[u][v] && !vis[v]) { vis[v] = 1; if(linker[v] == -1 || dfs(linker[v])) { linker[v] = u; return true; } } return false; } int hungary() { int res = 0; memset(linker,-1,sizeof(linker)); for(int u = 0;u < n;u++) { memset(vis,0,sizeof(vis)); if(dfs(u)) res++; } return res; } int main() { while(~scanf("%d",&n)) { memset(w,0,sizeof(w)); for(int i = 0;i < n;i++) { int num,ans; scanf("%d: (%d)",&num,&ans); while(ans--) { scanf("%d",&num); w[i][num] = 1; } } printf("%d\n",n - hungary() / 2); } return 0; }
相关推荐
pku acm 1466 Girls and Boys代码 二分图的最大匹配的匈牙利算法 解题报告请访问:http://blog.csdn.net/china8848
克隆回购: git clone https://github.com/ArturW1998/powerpuff-girls.git 安装依赖项: yarn install 启动项目: yarn start可用脚本yarn start在开发模式下运行该应用程序。 打开在浏览器中查看它。 webpack-dev...
One for the Girls! The Pleasures and Practices of Reading Women
数据集内包含训练集、测试集、验证集和每个商品对应的一张商品图像
Predicting reading achievement for Kindergarten boys and girls Psychology in rhr Schools Volunir 22. January. 1985 PREDICTING READING ACHIEVEMENT FOR KINDERGARTEN BOYS AND GIRLS NONA TOLLEFSON...
Personality factors of gifted boys and girls in middle childhood and adolescence AN INTERNSHIP PROGRAM IN SCHOOL PSYCHOLOGY-A WORKING MODEL 177 urban schools, suburban schools, special facilities ...
Syndromes of social maladaptation among elementary school boys and girls Psychology in the Schools 1982. 19, 281-286 SYNDROMES OF SOCIAL MALADAPTATION AMONG ELEMENTARY SCHOOL BOYS AND GIRLS ...
小学教案
Prevalence of reading failure in boys compared with girls Psychologv in rhe Schools Volume 31, January 1994 PREVALENCE OF READING FAILURE IN BOYS COMPARED WITH GIRLS JANE M. FLYNN Cognitive ...
★将Girls Und Panzer壁纸New Tab与所有freeaddons组合起来newtab-更多Girls Und Panzer动漫主题:https://freeaddon.com/?s=girls+und+panzer+anime+wallpaper+new+tab&post_type=post主页:https: //
3D-MAX Girls ---- png data
Wonder Girls.Nobody Wonder Girls.NobodyWonder Girls.Nobody
Girls 是一款看妹子的APP,Retrofit Rxjava,让网络请求和解析数据更轻松、直观
This study considered the utility of gender schema theory in examining girls’ website design preferences. It built on a previous study which identified eight website evaluation criteria related to ...
two girls dancing pics for python code. two girls dancing pics for python code. two girls dancing pics for python code. two girls dancing pics for python code.
微信小程序demo:基于node:wechat app of girls scrapy spider via Node.js(源代码+截图)微信小程序demo:基于node:wechat app of girls scrapy spider via Node.js(源代码+截图)微信小程序demo:基于node:wechat...
语言:English ... ★将女孩的Frontline壁纸新标签与所有FreeAddons Newtab - 更多女孩的前线动漫主题:https://freeaddon.com/?s=girls+frontline +Neme+wallpaper +New+Tab&Post_type =普斯特 主页:...
恶心视频2 Girls 1 Cup背景音乐钢琴曲谱双手数字简谱钢琴曲谱.pdf
1182 Keeps Going and Going and ... 简单题,我喜欢:) 1284 Perfection 简单题 1272 Numerically Speaking 简单题 1269 Coconuts, Revisited 简单题 1247 There s Treasure Everywhere! 简单题 1241 ...