2分图匹配算法

定义

• 节点u直接无边，v之间无边，边只存在uv之间。
• 判断方法：BFS染色法，全部染色后，相邻边不同色

无权二部图中的最大匹配

• 最大匹配即每一个都匹配上min（u， v）。
• 贪心算法可能导致，有些节点未匹配上
• 可以添加起始节点以及终止节点，使用网络流算法进行求解。

有权二部图中的最大匹配Maximum-Weight Bipartite Matching

• 每一条边都有权重，最大匹配追求的是整体的权重和最大。（整体收益最大）
• 最大匹配可以转化为最小匹配算法。即把权重*-1, 最小匹配的结果就是最大匹配的结果。
• 匈牙利算法可以解决最小匹配问题，但是u和v的节点数量需要保持一致，算法复杂度为O(n^3),暴力为O(n!)

匈牙利算法

• 构建u*u矩阵，没有边的为0

• 每一行减去每一行的最小值
  

• 每一列减去每一列的最小值
  

• 使用最小的线覆盖所有的0。如果线的数量小于u的数量，则剩下的继续找最小元素，然后递减，节点处加上该元素；如果数量相同，则优先找唯一有0的点进行匹配。
  
  
  
  

• 最大匹配结果可能不止1中，如5，2，3和5， 0， 5都是15。
  

• 如果uv节点不一致，可以通过补几个虚拟节点，权重设置为0，使得uv节点数量一致，那就可以用匈牙利算法求解了。

稳定婚配算法

• 一种特殊的2分图匹配问题
• 边由权重变成了顺序，而且是双向的
• 可以用gale-shapely算法求解
• 时间复杂度为O(n^2)

代码实现

• 通过找增广路径的方式进行求解
• 非匹配点出发，到非匹配点截至，中间为非匹配与匹配交替出现，然后变换状态即可。
• KM算法是加了权重的匈牙利算法，先把左边赋值最大权重，然后如果冲突，左边-detla, 右边+detla的操作，再通过增广路径求解。detla为lx+ly-weight
  https://blog.csdn.net/sidnee/article/details/106298615

https://blog.csdn.net/qq_37457202/article/details/80161274

参考：
https://www.bilibili.com/video/BV1G54y157HA/?spm_id_from=333.788&vd_source=d141bc07699831d8053b781fd6944d5f