Description
xiaoming实在太好管闲事了.有一天他去参加一个舞会,这里聚集了一大堆帅哥美女,但是舞会却不是那么顺利,虽然帅哥和美女的人数都是相同的,但并不是每一位帅哥都能找到他的舞伴,原因就是有些女生只愿意接受某些男生的邀请.小明为了舞会的顺利进行,xiaoming只好厚着脸皮去和这些女生搭话,了解到了这些女生就都愿意接受哪些男生的邀请,那么剩下的工作就是要小明给这些帅哥美女们搭搭线,小明只希望能找到舞伴的人尽量多.
Input
多组数据测试
每行一个偶数n(n<=1000) ,表示参加舞会的人数,其中男生和女生一样多。
接下来n/2行,每一行先是一个正整数m,然后是m个整数a1,a2…..am(ai<=n/2).
其中第i行表示,第i个女生只愿意接受m个男生的邀请,这分别是第a1,a2….am号男生
Output
在xiaoming的努力下,最多能有多少人找到自己的舞伴
Sample Input
8
1 3
2 2 4
1 2
1 2
Sample Output
6
Hint
一种组合方案是:1号女生和3号男生,2号女生和4号男生,3号女生和2号男生,那么只有4号女生和1号男生没有找到舞伴。
Source
Xiaoming@Fourth
思路:
二分图最大匹配,刚学会,理解不是很深入
相关知识:
http://www.cnblogs.com/pony1993/archive/2012/07/25/2607738.html
http://www.matrix67.com/blog/archives/39
http://imlazy.ycool.com/post.1603708.html
代码:
#include<iostream> using namespace std; #define N 505 int map[N][N],n1,n2,visit[N],Link[N]; int findroad(int x) { for(int i=1;i<=n2;i++) { if(map[x][i]&&!visit[i]) { visit[i] = 1; if(Link[i]==0||findroad(Link[i]))//x到i可到达,且增广路径上不存在重复点 { Link[i] = x; return 1; } } } return 0; } int main() { int n,ans; while(~scanf("%d",&n)) { memset(map,0,sizeof(map)); memset(Link,0,sizeof(Link)); ans = 0; n1 = n2 = n/2; for(int i=1;i<=n1;i++) { int num,a; scanf("%d",&num); for(int j=0;j<num;j++) { scanf("%d",&a); map[i][a] = 1; } } for(int i=1;i<=n1;i++) { memset(visit,0,sizeof(visit)); if(findroad(i)) ans++; } printf("%d\n",2*ans); } }
相关推荐
BOJ的题目1023. Ancient Keyboard解法 源代码
boj 上08 09 年复试模拟题的答案
JAVA_BOJ
boj:算法
Algorithm-BOJ.zip,BekJon在线法官(Java,Kotlin,SWIFT)和PS路线图,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
BOJ
Algorithm-BOJ-PSJ.zip,Baykon在线判断JAVA问题解决方法(第二章),算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
Algorithm-BOJ-AutoCommit.zip,当您解决baekjoon online judge的问题时,它会自动提交并推送到远程存储库。,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
Algorithm-boj-auto-submit.zip,日本央行cli提交脚本,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
资源分类:Python库 所属语言:Python 资源全名:boj-0.0.1.tar.gz 资源来源:官方 安装方法:https://lanzao.blog.csdn.net/article/details/101784059
通过这本图画书展示您的创造力,其中包括Boj和朋友。 一本有趣的,全数字化且可重复使用的着色书,可用于 通过这本图画书展示您的创造力,其中包括Boj和朋友。 一本有趣的全数字可重复使用的图画书,专为孩子,父母...
解决问题 Boj.kr
欢迎来到PS_BOJ 이곳은... J이한BOJ문제들의AC코드들이입니다。 안내 :check_mark: C ++ Python으로풀이합니다。 :check_mark: ++ C ++풀이하며 long long 필요하거나으으으으으으으으으끔씩만끔씩만끔씩만끔씩만...
BOJ:日本央行