博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
杭电2063--过山车(二分匹配)
阅读量:6570 次
发布时间:2019-06-24

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

过山车

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 14306    Accepted Submission(s): 6319

Problem Description
RPG girls今天和大家一起去游乐场玩,终于可以坐上梦寐以求的过山车了。可是,过山车的每一排只有两个座位,而且还有条不成文的规矩,就是每个女生必须找个个男生做partner和她同坐。但是,每个女孩都有各自的想法,举个例子把,Rabbit只愿意和XHD或PQK做partner,Grass只愿意和linle或LL做partner,PrincessSnow愿意和水域浪子或伪酷儿做partner。考虑到经费问题,boss刘决定只让找到partner的人去坐过山车,其他的人,嘿嘿,就站在下面看着吧。聪明的Acmer,你可以帮忙算算最多有多少对组合可以坐上过山车吗?
 

 

Input
输入数据的第一行是三个整数K , M , N,分别表示可能的组合数目,女生的人数,男生的人数。0<K<=1000
1<=N 和M<=500.接下来的K行,每行有两个数,分别表示女生Ai愿意和男生Bj做partner。最后一个0结束输入。
 

 

Output
对于每组数据,输出一个整数,表示可以坐上过山车的最多组合数。
 

 

Sample Input
6 3 3
1 1
1 2
1 3
2 1
2 3
3 1
0
 

 

Sample Output
3
 

 

Author
PrincessSnow
 

 

Source
 

 

Recommend
lcy   |   We have carefully selected several similar problems for you:            
最大独立集 = 顶点数 - 最小点覆盖数(最大匹配数)。
匈牙利算法:
 求最小点覆盖数。
 //二分匹配详解。
1 #include 
2 #include
3 #include
4 using namespace std; 5 int map[1010][1010]; //邻接矩阵存储关系; 6 int dis[1010]; //记录已匹配点的编号。 7 int vis[1010]; //标记数组; 8 int n, v; 9 bool Search(int a)10 {11 for(int i = 1; i <= v; i++)12 {13 if(map[a][i] && !vis[i]) //i与a相邻且未被标记; 14 {15 vis[i] = 1;16 if(dis[i] == 0 || Search(dis[i])) //i未出现在前一个匹配中 || i出现在前一个匹配中但从与i相邻的节点可能会有增广路; 17 {18 dis[i] = a;19 return true; 20 }21 }22 }23 return false; 24 }25 int main()26 {27 int m; 28 while(~scanf("%d", &m), m)29 {30 memset(map, 0, sizeof(map));31 memset(dis, 0, sizeof(dis));32 scanf("%d %d", &n, &v);33 for(int i = 1; i <= m; i++)34 {35 int a, b; 36 scanf("%d %d", &a, &b);37 map[a][b] = 1;38 }39 int cnt = 0;40 for(int i = 1; i <= n; i++)41 {42 memset(vis, 0, sizeof(vis));43 if(Search(i))44 cnt++;45 }46 printf("%d\n", cnt);47 }48 return 0; 49 }

 

转载于:https://www.cnblogs.com/soTired/p/4743308.html

你可能感兴趣的文章
用windows浏览器打开Linux的Jupyter notebook开发、调试示例
查看>>
PsySH——PHP交互式控制台
查看>>
winform路径
查看>>
Linux文件与目录隐藏权限
查看>>
中国民航飞行学院人事薪资管理系统实践案例
查看>>
MVVM架构~knockoutjs系列之验证信息自定义输出
查看>>
PTA编程总结1:打印沙漏
查看>>
mac git从代码仓库克隆代码,修改并上传
查看>>
数据结构-循环单链表之魔术师发牌问题
查看>>
ssm(4)整合
查看>>
.net Windows服务程序安装与安装程序的制作
查看>>
感悟还是教训,或者。。。
查看>>
node.js模块中exports和module.exports的区别
查看>>
sleep()和wait()的区别 --- 快入睡了,突然想起一个知识点,搞完就睡
查看>>
Linux各目录的作用
查看>>
迄今为止 .Net 平台功能最强大,性能最佳的 JSON 序列化和反序列化库。
查看>>
PHP中使用socket通信响应速度慢的原因与解决办法
查看>>
shell中的变量a=100, 什么时候作整数使用, 什么时候作字符串使用呢?
查看>>
软件开发从业者如何走出自己的安逸环境[转]
查看>>
Python学习笔记<资源收录>
查看>>