【模板】二分图最大权完美匹配KM算法

hdu2255模板题

KM是什么意思，详见百度百科。

总之知道它可以求二分图最大权完美匹配就可以了，时间复杂度为O(n^3)。

给张图。

二分图有了边权，求最大匹配下的最大权值。

所以该怎么做呢？对啊，怎么做呢？

我也不懂啊，看的别人博客。

然而并没有将思路，只是模拟了一遍。

核心是在当两个女生都匹配到一个男生时，这两个女生只能降低一下期望值了，降低多少呢？两个妹子都在能选择的其他人中，也就是没参与这轮匹配的男生中，选择一个期望值降低的尽可能小的人。也就是再其他人中选择一个最合适的。

匹配过程用匈牙利算法。

——代码（服用时把注释去掉就好）

1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 5 using namespace std; 6 7 const int INF = 0x3f3f3f3f; 8 const int maxn = 301; 9 int n; 10 int love[maxn][maxn]; 11 //男女好感度 12 int ex_boy[maxn], ex_girl[maxn]; 13 //每个男生期望值，每个妹子期望值 14 int match[maxn]; 15 //记录每个男生匹配到的妹子 如果没有则为1 16 int slack[maxn]; 17 //记录每个男生如果能被妹子倾心最少还需要多少期望值 18 bool vis_boy[maxn], vis_girl[maxn]; 19 //记录每一轮匹配匹配到的男生和女生 20 21 bool find(int i) 22 38 } 39 else slack[j] = min(slack[j], gap); 40 // slack 可以理解为该男生要得到女生的倾心 还需多少期望值 取最小值 备胎的样子【捂脸 41 } 42 return 0; 43 } 44 45 int KM() 46 89 } 90 } 91 92 //匹配完成，找出所有匹配的好感度之和 93 for(i = 1; i <= n; i++) ret += love[match[i]][i]; 94 return ret; 95 } 96 97 int main() 98 107 return 0; 108 }
View Code

拉闸，变量名改不过来了。

上一篇：[洛谷P2580]于是他错误的点名开始了（Trie树）

下一篇：【模板】网络最大流

---

二分图 模板 最大权完美匹配 KM算法