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