二分图匹配问题
二分图匹配问题
问题
在一个二分图中,每一个点只能匹配一个点,求这个图中最多能存在多少对匹配上的点。
匈牙利算法
dfs(i)
函数为尝试让 i
进行匹配的函数,如果 i
号点可以进行匹配,则答案 ans++
。
dfs
函数的原理为:首先对与 i
号点有边的点尝试匹配,如果该点已经被匹配,则尝试让该点匹配的点重新匹配,如果匹配成功,修改该点匹配的点为 i
否则尝试下一个点。
算法代码
1 | int n, m; |
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Ender's Blog!
评论