KM是什么意思，详见百度百科。
总之知道它可以求二分图最大权完美匹配就可以了，时间复杂度为O(n^3)。
给张图。
二分图有了边权，求最大匹配下的最大权值。
所以该怎么做呢？对啊，怎么做呢？
我也不懂啊，看的别人博客。
然而并没有将思路，只是模拟了一遍。
核心是在当两个女生都匹配到一个男生时，这两个女生只能降低一下期望值了，降低多少呢？两个妹子都在能选择的其他人中，也就是没参与这轮匹配的男生中，选择一个期望值降低的尽可能小的人。也就是再其他人中选择一个最合适的。
匹配过程用匈牙利算法。
——代码（服用时把注释去掉就好）
#include <iostream>
#include <cstdio>
#include <cstring> using namespace std; const int INF = 0x3f3f3f3f;
const int maxn = ;
int n;
int love[maxn][maxn];
//男女好感度
int ex_boy[maxn], ex_girl[maxn];
//每个男生期望值，每个妹子期望值
int match[maxn];
//记录每个男生匹配到的妹子 如果没有则为-1
int slack[maxn];
//记录每个男生如果能被妹子倾心最少还需要多少期望值
bool vis_boy[maxn], vis_girl[maxn];
//记录每一轮匹配匹配到的男生和女生 bool find(int i)
{
int j, gap;
vis_girl[i] = ;
for(j = ; j <= n; j++)
{
if(vis_boy[j]) continue; //每一轮匹配，每个男生只尝试一次
gap = ex_girl[i] + ex_boy[j] - love[i][j];
if(gap == ) //如果符合要求
{
vis_boy[j] = ;
//如果没有找到匹配男生，或者该男生的妹子可以找到其他人
if(match[j] == - || find(match[j]))
{
match[j] = i;
return ;
}
}
else slack[j] = min(slack[j], gap);
// slack 可以理解为该男生要得到女生的倾心 还需多少期望值 取最小值 备胎的样子【捂脸
}
return ;
} int KM()
{
int i, j, d, ret = ;
memset(match, -, sizeof(match));
//初始每个男生都没有匹配到女生
memset(ex_boy, , sizeof(ex_boy));
//初始每个男生期望值为0 //每个女生的期望值是与她相连的男生的最大好感度
for(i = ; i <= n; i++)
for(j = ; j <= n; j++)
ex_girl[i] = max(ex_girl[i], love[i][j]); //尝试为每个女生解决归宿问题
for(i = ; i <= n; i++)
{
memset(slack, / , sizeof(slack));
//因为要取小值，初始化无穷大
while()
{
//为每个女生解决归宿的方法是：
//如果找不到就降低期望值，直到找到为止 //记录每轮匹配中男女是否被匹配过
memset(vis_girl, , sizeof(vis_girl));
memset(vis_boy, , sizeof(vis_boy)); //找到归宿，退出
if(find(i)) break; //如果找不到，就降低期望值
//最小可降低的期望值
d = INF;
for(j = ; j <= n; j++)
if(!vis_boy[j])
d = min(d, slack[j]); for(j = ; j <= n; j++)
{
//所有访问过的妹子降低期望值
if(vis_girl[j]) ex_girl[j] -= d;
//所有访问过的男生增加期望值
if(vis_boy[j]) ex_boy[j] += d;
}
}
} //匹配完成，找出所有匹配的好感度之和
for(i = ; i <= n; i++) ret += love[match[i]][i];
return ret;
} int main()
{
int i, j;
while(~scanf("%d", &n))
{
for(i = ; i <= n; i++)
for(j = ; j <= n; j++)
scanf("%d", &love[i][j]);
printf("%d\n", KM());
}
return ;
}
拉闸，变量名改不过来了。
