匈牙利算法的一些思考

时间：2020-02-07 09:02:35 阅读：77 评论：0 收藏：0 [点我收藏+]

因为vis[k]已经标记过了在本轮之后的匹配中k不会再被选中第i个人能否选k依赖于第i个人选k （前i-1个人中)第i-1轮中匹配过的(记为m个)能否都匹配成功
前i-1轮中匹配过的能否都匹配成功依赖于之前与k匹配的选其它他能匹配的剩余m-1人能否都匹配成功
故得一直递归到只剩一人时能否匹配成功
这也说明了为第i个人匹配的同时保证之前匹配过的人依然有匹配

vis[k]表示本轮已经匹配过了k
要么匹配成功 find函数返回
要么表示无法给之前与k匹配的重新匹配

第i个人能选k k要么在之前没匹配过要么和k匹配的还可以选别人

匈牙利算法只是为冲突的重新匹配不冲突的不变

为第i人匹配时先重置vis

若之前与k匹配的无法选别人而被标记了也不会影响结果

越到后面vis被标记得更多，限制得越多前面都不行更何况后面

vis[k]=1表示本轮k已经访问过了

因为之后再用到k 还是要给之前与k匹配的匹配别人

lk是被匹配的连向匹配的边
第i轮的lk是第i-1轮匹配完成后的lk
只有匹配成功才会修改lk 而匹配成功 find函数也就返回了
故第i轮匹配的过程中lk数组不变

匈牙利算法的一些思考

原文：https://www.cnblogs.com/wyh447154317/p/12271342.html

踩

(0)

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)