带权二分图匹配（KM算法）

Problem Description
传说在遥远的地方有一个非常富裕的村落,有一天,村长决定进行制度改革：重新分配房子。
这可是一件大事,关系到人民的住房问题啊。村里共有n间房间,刚好有n家老百姓,考虑到每家都要有房住（如果有老百姓没房子住的话，容易引起不安定因素），每家必须分配到一间房子且只能得到一间房子。
另一方面,村长和另外的村领导希望得到最大的效益,这样村里的机构才会有钱.由于老百姓都比较富裕,他们都能对每一间房子在他们的经济范围内出一定的价格,比如有3间房子,一家老百姓可以对第一间出10万,对第2间出2万,对第3间出20万.(当然是在他们的经济范围内).现在这个问题就是村领导怎样分配房子才能使收入最大.(村民即使有钱购买一间房子但不一定能买到,要看村领导分配的).

Input
输入数据包含多组测试用例，每组数据的第一行输入n,表示房子的数量(也是老百姓家的数量)，接下来有n行,每行n个数表示第i个村名对第j间房出的价格(n<=300)。

Output
请对每组数据输出最大的收入值，每组的输出占一行。

Sample Input
2
100 10
15 23

Sample Output
123

KM算法
https://blog.csdn.net/guoyangfan_/article/details/83064499

#include <bits/stdc++.h>
using namespace std;
const int maxn = 305;
int w[maxn][maxn];
int lx[maxn], ly[maxn];
int visx[maxn], visy[maxn];
int match[maxn];
int n, delta;
const int inf = 1<<30;
int dfs(int u) {
	visx[u] = 1;/*当前点（x)参与了这次dfs，将其标记*/
	for (int i = 1; i <= n; i++) {/*由题意，我们要选择所有可能的人组队*/
		if (!visy[i]) {/*如果要去匹配的点在本次操作中还没有操作过*/
			int tmp = lx[u] + ly[i] - w[u][i];
			if (tmp == 0) {
				visy[i] = 1;
				if (match[i] == 0 || dfs(match[i])) {
					match[i] = u;
					return 1;/*可以找到在当前顶标的其他匹配点*/
				}
			} else if (tmp > 0){
				delta = min(delta, tmp);/*找不到了，试图减小参与本次dfs的顶标*/
			}
		}
	}
	return 0;
}

void KM() {
	memset(match, 0, sizeof(match));
	memset(lx, 0, sizeof(lx));
	memset(ly, 0, sizeof(ly));
	for (int i = 1; i <= n; i++) 
		for (int j = 1; j <= n; j++) 
			lx[i] = max(lx[i], w[i][j]);
	for (int i = 1; i <= n; i++) {
		while (1) {
			memset(visx, 0, sizeof(visx));
			memset(visy, 0, sizeof(visy)); /*每***作的预处理，表示在当前dfs中，是否操作过*/
			delta = inf;
			if (dfs(i)) break;/*如果可以将当前点之前的点的匹配点换掉且顶标不变，那么我们直接跳过下面的步骤,寻找下一个点的匹配方案*/
			for (int j = 1; j <= n; j++) {/*我们根据步骤操作，左边节点-date,右边节点+date*/
				if (visx[j]) lx[j] -= delta;
				if (visy[j]) ly[j] += delta;
			}
		}
	}
}



int main() {
	while (~scanf("%d", &n)) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				scanf("%d", &w[i][j]);
			}
		}
		KM();
		int ans = 0;
		for (int i = 1; i <= n; i++) {
			ans += w[match[i]][i];
		}
		printf("%d\n", ans); 
	}
	
	return 0;
}

现在有N男N女，有些男生和女生之间互相有好感，我们将其好感程度定义为好感度，我们希望把他们两两配对，并且最后希望好感度和最大。

KM算法详解-wenr

怎么选择最优的配对方法呢？

首先，每个女生会有一个期望值，就是与她有好感度的男生中最大的好感度。男生呢，期望值为0，就是……只要有一个妹子就可以啦，不挑~~

这样，我们把每个人的期望值标出来。

注：这里所说的期望值用专用名词表示是顶标，全称顶点标记值。

注：这里所说的女生对男生的好感度（也就是我们看见的所有边）正式表达起来是w(i,j)。

KM算法详解-wenr

接下来，开始配对。

配对方法：

我们从第一个女生开始，分别为每一个女生找对象。

每次都从第一个男生开始，选择一个男生，使男女两人的期望和要等于两人之间的好感度。

注意：每一轮匹配，每个男生只会被尝试匹配一次！

具体匹配过程：

为女1找对象=

（此时无人配对成功）

根据 “男女两人的期望和要等于两人之间的好感度”的规则

女1-男1：4+0 != 3

女1-男3：4+0 == 4

所以女1选择了男3

女1找对象成功

==为女1找对象成功

为女2找对象=

（此时女1—男3）

根据配对原则，女2选择男3

男3有主女1，女1尝试换人

我们尝试让女1去找别人

尝试失败

为女2找对象失败！

==为女2找对象失败

这一轮参与匹配的人有：女1，女2，男3。

怎么办？？？很容易想到的，这两个女生只能降低一下期望值了，降低多少呢？

任意一个参与匹配女生能换到任意一个这轮没有被选择过的男生所需要降低的最小值

比如：女1选择男1，期望值要降低1。女2选择男1，期望值要降低1。女2选择男2，期望值要降低2。

于是，只要期望值降低1，就有妹子可能选择其他人。所以妹子们的期望值要降低1点。

同时，刚才被抢的男生此时非常得意，因为有妹子来抢他，于是他的期望值提高了1点（就是同妹子们降低的期望值相同）。

于是期望值变成这样（当然，不参与刚才匹配过程的人期望值不变）

KM详解-wenr

==继续为女2找对象=

（此时女1—男3）

女2选择了男1

男1还没有被配对

女2找对象成功！

==为女2找对象成功=

为女3找对象=

（此时女1—男3，女2-男1）

女3没有可以配对的男生……

女3找对象失败

==为女3找对象失败

此轮只有女3参与匹配

此时应该为女3降低期望值

降低期望值1的时候，女3-男3可以配对，所以女3降低期望值1

KM算法详解

==继续为女3找对象

（此时女1—男3，女2-男1）

女3相中了男3

此时男3已经有主女1，于是女1尝试换人

女1选择男1

而男1也已经有主女2，女2尝试换人

前面说过，每一轮匹配每个男生只被匹配一次

所以女2换人失败

女3找对象再次失败

==为女3找对象失败

这一轮匹配相关人员：女1，女2，女3，男1，男3

此时，只要女2降低1点期望值，就能换到男2

（前面提过只要任意一个女生能换到任意一个没有被选择过的男生所需要降低的最小值）

我们把相应人员期望值改变一下

KM算法详解-wenr

==还是为女3找对象

（此时女1—男3，女2-男1）

女3选择了男3

男3有主女1，女1尝试换人

女1换到了男1

男1已经有主女2，女2尝试换人

女2换人男2

男2无主，匹配成功！！！

==为女3找对象成功=

匹配成功！！！撒花~~

到此匹配全部结束

此时

女1-男1，女2-男2，女3-男3

好感度和为最大：9

虽然不停换人的过程听起来很麻烦，但其实整个是个递归的过程，实现起来比较简单。比较复杂的部分就是期望值的改变，但是可以在递归匹配的过程中顺带求出来。

------------------------------转载部分分割线-------------------------------