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
拉闸，变量名改不过来了。
上一篇：[HNOI2009]梦幻布丁（链表+启发式合并）
下一篇：[HDU3062]Party（2-sat）
模板 二分图 KM算法 最大权完美匹配
