博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
hdu 1068 Girls and Boys
阅读量:5821 次
发布时间:2019-06-18

本文共 2222 字,大约阅读时间需要 7 分钟。

Girls and Boys

Time Limit: 20000/10000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 6148    Accepted Submission(s): 2750

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
 

 

Recommend
JGShining
 
1 //2500MS    4188K    944 B    G++ 2 //求最大独立集,二分匹配模板题,首先要知道匈牙利算法,之后就好解了  3 //最大独立集: 总人数减去最大匹配书结果为最大独立数  4 #include
5 #include
6 int g[1005][1005]; 7 int match[1005]; 8 int vis[1005]; 9 int n;10 bool dfs(int x)11 {12 for(int i=1;i<=n;i++){13 if(!vis[i] && g[x][i]){14 vis[i]=1;15 if(match[i]==0 || dfs(match[i])){ 16 match[i]=x;17 return true;18 }19 }20 }21 return false;22 }23 int hungary()24 {25 int ans=0;26 memset(match,0,sizeof(match));27 for(int i=1;i<=n;i++){28 memset(vis,0,sizeof(vis));29 vis[i]=1;30 if(dfs(i)) ans++;31 }32 return ans;33 }34 int main(void)35 {36 int a,m,b;37 while(scanf("%d",&n)!=EOF) 38 {39 memset(g,0,sizeof(g));40 for(int i=0;i

 

转载于:https://www.cnblogs.com/GO-NO-1/articles/3339884.html

你可能感兴趣的文章
node-express项目的搭建并通过mongoose操作MongoDB实现增删改查分页排序(四)
查看>>
如何创建Servlet
查看>>
.NET 设计规范--.NET约定、惯用法与模式-2.框架设计基础
查看>>
win7 64位+Oracle 11g 64位下使用 PL/SQL Developer 的解决办法
查看>>
BZOJ1997:[HNOI2010]PLANAR——题解
查看>>
BZOJ1014:[JSOI2008]火星人prefix——题解
查看>>
使用Unity3D引擎开发赛车游戏
查看>>
HTML5新手入门指南
查看>>
opennebula 开发记录
查看>>
ubuntu 修改hostname
查看>>
sql 内联,左联,右联,全联
查看>>
C++关于字符串的处理
查看>>
6、Web Service-拦截器
查看>>
Flask 源码流程,上下文管理
查看>>
stream classdesc serialVersionUID = -7218828885279815404, local class serialVersionUID = 1.
查看>>
ZAB与Paxos算法的联系与区别
查看>>
java 读取本地的json文件
查看>>
Breaking parallel loops in .NET C# using the Stop method z
查看>>
Android Content Provider Guides
查看>>
修改故障转移群集心跳时间
查看>>