【附加题】n男n女去相亲，活动结束时两两异性间产生匹配值，用

[问答题]

【附加题】n男n女去相亲，活动结束时两两异性间产生匹配值，用1-100整数表示。为了使活动完美，主办方希望找到一种匹配方案，使得所有异性两两匹配，并且中匹配值最大。

1）编程实现匹配算法，并分析时间算法复杂度，估算在你的计算机上n能支持到多大

2）当n比较大时，可能接受次优解，请描述可以怎么优化你的算法或使用别的算法

-半`城烟`沙つ

简易算法可以使用二分图最大匹配算法：KM算法用O(n^3)的复杂度解决；

优化方法是考虑用网络流来处理

男的作为二分图左部节点，女的作为二分图右部节点，把男女匹配值连边，在左部建立超级源点S，把S连向所有的左部节点，右部建立超级汇点T，把所有右部节点连向T，用Dinic算法可以用O(n^2√n)的复杂度实现，大概能跑过5*10^3的数据

发表于 2019-10-11 14:20:44 回复(0)

tanqb

二分图的最大权匹配，KM算法。。

发表于 2019-10-11 11:30:54 回复(0)

提交观点

问题信息

C++工程师 4399游戏 2017 Java工程师销售

来自：职能类模拟题1

上传者：牛妹

难度：

2条回答 13收藏 2111浏览

扫一扫，把题目装进口袋