二分图匹配，Hangarian算法， Kuhn

算法， Kuhn"/>

二分图匹配，Hangarian算法， Kuhn

一. 看到的比较好的文章：

图论总结（一）二分图最大匹配_LinHunYoR的博客-CSDN博客_二分图最大匹配://brc2/the-algorithm-workshop//

匈牙利算法(Kuhn-Munkres)算法_17420的博客-CSDN博客_munkres算法

二、二分图最优匹配：

匹配：在二分图G的一个子图M中， M的边集{E}中的任意两条边都不交汇于同一个结点，则称M是一个匹配

最优匹配：M的边数最多（边无权重， Hangarian 算法）， 或者是边的权重（costs）和最小（Kuhn-Munkres算法）

三、一些开源实现：

3.1 Munkres-cpp: ://github/saebyn/munkres-cpp简介：1）基于c++的带权（cost）的二分图匹配，希望权重的和最小， inplace改变costs matrix的值；2）没有办法表示不相连的顶点， 效率上稍微低一些；

正常输出：0的地方表示匹配的位置

solve的时间：50x50的矩阵大概在10ms左右：