4.5腾讯笔试 第三题
将机器与任务作为结点，可分配关系作为连线，构造二分图。使用匈牙利算法先找到一个最大匹配。将任务结点按照value值排序，从value值高的遍历一遍，若有未分配任务结点，从该结点开始，寻找一条偶数长度，波浪线与直线交替的路径，其中波浪线表示未分配，直线表示分配，并且尾点的value值较低。如果能找到这样的路径，则将波浪线与直线替换，即得到一个新的匹配，并且能保持最大数量不变，总的value值上升，遍历完就能得到最大的总value值。#春招##实习##笔试题目##腾讯#
2018-04-17 14:16 已编辑 中山大学 C++
关注
全部评论
ElliotChanX
华为_智能车解决方案_软件工程师
膜拜大佬，看到这道题的第一思路就这么复杂....我就只能用贪心
仅凭一把砍刀闯天下
复旦大学 算法工程师
直接是裸的费用流。。。搞这么麻烦。
nodekey
武汉科技大学 C++
老哥 这真的行么…… 就说匈牙利在这个图的复杂度怎么说也是 O(n^2) 吧，再说这个图你要怎么记录，边数极限情况 1e10 级别的……
相关推荐
05-19 19:57
蚌埠学院 Python 
2237：Gpa70不算高，建议只写排名，个人技能不在多而在精，缩到8条以内。项目留一个含金量高的，减少间距弄到一页，硕士简历也就一页，本科不要写很多 点赞 评论 收藏
分享
06-06 15:43
黑龙江外国语学院 Java 点赞 评论 收藏
分享
