这个二分图匹配问题是否有可行算法能解
二分图匹配问题，行、列分别构成n个节点共2n个点，+1是连接行、列的边，找最大匹配
■网友
补充几点首先，操作是否成功跟操作顺序有关。比如一个2*2矩阵，第一行全是+1，第二行第一列是+1，第二列是-1。如果先操作第一行第一列的+1，剩下一个-1，操作失败；如果先操作第二行第一列的+1，则剩下一个+1可以继续操作，此时操作成功。其次，操作是否成功跟+1的多少没有明显关系，反而跟+1的位置有关。最极端的情况下全部对角线是+1，其他元素全为-1也可以操作成功。相反，所有的+1都在第一行，其他元素全为-1，则无法操作成功。不知道有没人知道这个问题在数学上有没有专业的叫法，有没有人研究过？如果没有的话，初步想法是，将矩阵进行行列变换，然后分块，把所有-1集中到一个方阵里，再研究方阵之外+1的分布情况？目前还没找到如何判断操作无法成功的充分必要条件。。。。
■网友
可以用二分图匹配来解决该问题。建立二分图，第一部分用n个节点代表n行，第二部分用n个节点代表n列。如果x行y列处数值为+1，则给第一部分中的x号节点和第二部分中的y号节点之间连上一条边。然后就是二分图的匹配问题了，目前算法复杂度最低的是Hopcroft-Karp算法。该算法由John.E.Hopcroft和Richard M.Karp于1973提出，算法复杂度为O（n^0.5*m），其中n为二分图的顶点数，m为二分图中的边数。二分图最大匹配之Hopcroft-Karp算法
推荐阅读
- 如果你的多肉出现这个长势，要注意这个细节，多肉才会越来越美！
- 『活动』让孩子们欢欢喜喜过新年 这个元旦好有爱！南京聋校举办多种形式庆祝活动
- 免费“单人套餐”背后的故事：爱心让这个冬天不再寒冷
- 夫子庙■“秦淮灯会”“夫子庙小吃”等非遗重点保护 护航夫子庙，这个法明年施行
- 气温■@江苏人，这个周末天气晴！温度缓慢回升，早晚依旧“冻”人
- 黄金时间■黄金时间丨哪种产品最节水？购买产品请注意这个标识！
- 『黄金时间』请认准这个蓝色的标志！ 黄金时间丨同行业中用水最少的企业
- 汽车|评测 | 懂你所想，予你所需！依维柯欧胜2021款这个“搭档”可还行？
- 电动车|这个月，原来小编们这么拼
- 汽车娱生活|日产推出全新“小途乐”，20万就能入手？匹配四驱+三把锁