KM 二分图最大权匹配。

可以说是抄的ix35的洛谷博客了。。。。。

改写

首先要讲最大权匹配改写成线性规划形式。 \[ \begin{aligned} \max \sum_{i\leq m}w_ix_i\\ s.t. \forall i\leq n,\sum_{j\leq m}w(i,j)x_j\leq 1 \end{aligned} \] \(x_i\) 代表着每条边选不选。

\(w(i,j)\) 表示 一条边 \(j\) 的一端是不是 \(i\)。

将这个东西转成对偶形式（暂时不会证明对偶等价于原问题/kk，待填） \[ \begin{aligned} \min \sum_{i\leq n}y_i\\ s.t. \forall i\leq m,\sum_{j\leq n}w(i,j)y_i\geq w_i \end{aligned} \] 含义变为 给每一点选一个正权值 \(y_i\)。

使得对于每一条边，边权小于两端点权和。

---

第一次转化

二分图最大权匹配，我们要将他转化为，最大权完美匹配。

不存在负权，那就添加虚点，和对面点连 0 权边。

存在负权，最大匹配不可能包含负权边，无视负权即可。

存在负权完美匹配，没有边设为 \(-\infin\)

---

第二次转化

我们说，如果现在我们把 \(w_x+w_y=e(x,y)\) 满足的边保留，如果现在存在一个完美匹配，那么这个就是最大完美匹配。

原因：考虑完美匹配 \(\sum w_i\leq \sum_{x\in \mathrm{l}} w_x+\sum_{x\in\mathrm{r}}w_x\)

将相等边保留，恰好是一个取等条件。注意看上面的对偶形式，上界恰好就是我们要minimize的东西。

现在我们的目标是给 \(a,b\) 赋值使得满足相等边有完美匹配。

---

调整法

对于增广路，很神奇的是，有这样一种调整方法，我们将左部点\(-d\)，将右部点 \(+d\)，而初始增广点也是左部点 \(-d\)。

这样如果当前二分图依然合法，那么我们的\(\sum w\) 下降了 \(d\)。进一步的，我们将左部点减小，那么很有可能产生新的增广边，使得匹配数增加。

显然不可能无条件减，bound就是 \(w_i+w_j-d\ge e(i,j)\)，其中 \(i\) 是增广路上的左部点,\(j\) 是不在 增广路上的右部点。

\(d\leq w_i+w_j-e(i,j)\) 这样\(d\) 很有可能是 0，让我们无功而返。

那么我们就应该把整个增广网络拿出来，在进行上述判断。

此时我们想一下，如果d到达了非零上界 $ w_i+w_j-e(i,j)$ 此时必然会使增广路边长，匹配数变大。可以发现最多增广 \(O(n)\) 次。

对于右部点记录 \(slack_i\) 表示 \(\min_{j} ( w_i+w_j-e(i,j))\) 。

每次最后被增广的点 \(x\) ，选择一个最小的 \(slack_y\) ，通过减去 \(slack_y\)，尝试将 \(y\) 增广，注意此时可能 \(x\to y\) 并不是相等路。

所以需要记录一下 \(slack\) 的 \(argmin\) 位置，而增广 \(y\) 是从 \(argmin\) 而并非 \(x\) 而来（虽然 argmin 可能等于 x）。

中止条件就是成功使匹配数++。

注意：本质上我们在维护一堆增广路。

void bfs (int x) {
	memset(vis,0,sizeof(vis));
	memset(s,0x3f,sizeof(s));
	memset(pre,0,sizeof(pre));
    int cur;
	cur=0,mat[0]=x;
	while (1) {
		x=mat[cur];
		vis[cur]=1;
        int pos=0;
		for (int i=n+1;i<=n+n;i++) {
			if (vis[i]) {continue;}
			int tmp=w[i]+w[x]-d[x][i];
			if (tmp<s[i]) pre[i]=cur;
            s[i]=min(s[i],tmp);
			if (s[i]<=s[pos]) {pos=i;}
		}
        int dis=s[pos];
		w[mat[0]]-=dis;
		for(int y=n+1;y<=2*n;y++){
            if(vis[y]) w[y]+=dis,w[mat[y]]-=dis;
            else s[y]-=dis;
        }
		cur=pos;
		if (!mat[pos]) {break;}
	}
	while (cur) {
		mat[cur]=mat[pre[cur]];
		cur=pre[cur];
	}
	return;
}

也就是说我们并不能想当然的认为是按照bfs的顺序增广的，所以需要记录 pre （argmin）。