浅谈km算法解决二分图最大权匹配问题（附二分图基本定理证明）
前置知识：
熟练的掌握二分图基本知识，会运用二分图染色和最大匹配。（好像并没什么用
二分图匹配大家都知道吧，二分图最大匹配大家也多知道吧，这里就不过多的进行讲述。其实是我懒得写。
可以看一下我这篇题解：超级英雄
对了推荐一个动态模拟二分图匹配的网址，超级好用：透彻
引子
下面引入这样一个问题：
\(GMP\)琛哥在放假回来后带了一堆零食，立刻被\(ghj1222\)，锤子和真硕看到了，他们说，琛哥，我看你这行吗？
琛哥没同意，然后他就把雷哥控制住了（QAQ好像哪里不对（大雾。
锤子，ghj，真硕就开始分琛哥的零食。每个人对不同的零食都有自己的偷税值。
怎么分零食，才能让所有人偷税值最大？
这就涉及到一个问题：二分图最大权匹配。
即：对于一个二分图，最大匹配的方式可能是不唯一的，如果给每一条边付上权值，会存在一个匹配使权值之和最大。
\(part\ one\)
引用某两个巨佬博客里的一句话：
二分图是特殊的网络流，二分图最大匹配可以用Dinic算法解决。二分图最大权匹配相当最小费用最大流可以用FF算法。
我那么菜，学不会网络流，还是学点简单的吧。
下面进入正题
km算法就可以来解决这个问题。不过有一个前提是这个匹配情况是要在完全匹配（就是各个点都能一一对应另一个点）。(如果只是想求最大权值匹配而不要求是完全匹配的话，请把各个不相连的边的权值设置为0。 )(这里我还不太明白)
二分图最大权匹配他也是二分图匹配啊，同时还是一种特殊的网络流，结合他们的思想，我们可以这样想：每次找最大边进行连边，那如果有一个点被比匹配过怎么办，用匈牙利算法来改变匹配。
所以km算法的思路就是：每次找最大的边连边，如果不能就换一条较大的。
下面要解决的一个问题就是：如何找该点对应的权值最大的边？
\(part\ two\)
继续上面的问题：如何找该点对应的权值最大的边？
km算法比较NB的地方来了:设立标杆
对于每个\(x_i，y_i\)，设立一个标杆\(C_x，C_y\)。
满足\(C_x+C_y>=w_{x,y}\)
- 初始化
\(C_x=max(C_x,w_{x,y});\)
\(C_y=0;\)
(我还是不知道为什么QAQ？？？)
- 连边
用匈牙利算法，判断两点之间能否连线，再将最大边连线。这里把\(w_{x,y}==0\)的条件换成了\(C_x+C_y==w_{x,y}\)
- (所以链式前向星没法做吧？（大雾)
\(part\ three\)
此时，有了一个新的名词——相等子图
我们现在已经可以让计算机连接最大的边
\(part\ five\)
\(if\)要求边权值最小的匹配呢？？？
我们可以把边权值取负值，得出结果后再取相反数就可以了。
\(Code\)
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int qwq=0x7fffffff;
int w[1000][1000]; //w数组记录边权值
int line[1000],usex[1000],usey[1000],cx[1000],cy[1000]; //line数组记录右边端点所连的左端点，usex，usey数组记录是否曾访问过，也是判断是否在增广路上，cx，cy数组就是记录点的顶标
int n,ans,m; //n左m右
bool find(int x){
usex[x]=1;
for (int i=1;i<=m;i++){
if ((usey[i]==0)&&(cx[x]+cy[i]==w[x][i])){ //如果这个点未访问过并且它是子图里面的边
usey[i]=1;
if ((line[i]==0)||find(line[i])){ //如果这个点未匹配或者匹配点能更改
line[i]=x;
return true;
}
}
}
return false;
}
int km(){
for (int i=1;i<=n;i++){ //分别对左边点依次匹配
while (true){
int d=qwq;
memset(usex,0,sizeof(usex));
memset(usey,0,sizeof(usey));
if (find(i)) break; //直到成功匹配才换下一个点匹配
for (int j=1;j<=n;j++)
if (usex[j])
for (int k=1;k<=m;k++)
if (!usey[k]) d=min(d,cx[j]+cy[k]-w[j][k]); //计算d值
if (d==qwq) return -1; //不存在完全匹配。//没有用
for (int j=1;j<=n;j++)
if (usex[j]) cx[j]-=d;
for (int j=1;j<=m;j++)
if (usey[j]) cy[j]+=d; //添加新边
}
}
ans=0;
for (int i=1;i<=m;i++)
ans+=w[line[i]][i];
return ans;
}
int main(){
while (~scanf("%d%d",&n,&m)){
memset(cy,0,sizeof(cy));
memset(w,0,sizeof(w));
memset(cx,0,sizeof(cx));
for (int i=1;i<=n;i++){
int d=0;
for (int j=1;j<=n;j++){
scanf("%d",&w[i][j]);
d=max(d,w[i][j]); //此处顺便初始化左边点的顶标
}
cx[i]=d;
}
memset(line,0,sizeof(line));
printf("%d\n",km());
}
return 0;
}
KM算法习题
\(U53388\)
运动员最佳匹配问题
附（大雾
二分图定理的一些证明：
1.最小顶点覆盖
定义：能覆盖所有的边的最少顶点数(或是最小点权和)
最小顶点覆盖 = 最大匹配数
证明：假设最大匹配是M。为了求最少的点让每条边都至少和期中一个点关联。 M个点是足够的。就是说他们覆盖最大匹配的那M条边后，假设有某边没被覆盖，那么把它加入后会得到一个更大的匹配，出现矛盾。 M个点是必需的。匹配的M条边，由于他们两两无公共点，就是说至少有M个点才能把他们覆盖，所以啊，最小顶点覆盖 = 最大匹配数 。
2.最大独立点集
定义：在二分图中，选择一些点，使得这些点两两没有边直接相连。
最大独立点集=总点数-最小顶点覆盖
证明：可以这么想，最小顶点覆盖里的每一个点，会去尽可能多的覆盖更多的边，这样一来，这个点覆盖的边的对面的一群点，就全会被算到最大独立点集中，如果最大独立点集中的点有边，那最大匹配数会更优，最小顶点覆盖 也会更大，所以最大独立点集=总点数-最小顶点覆盖。
3.DAG最小路径覆盖
定义：能覆盖所有点的最少路径数
最小路径覆盖 = 原图上的点数 - 最大匹配数
证明：先说一下建图
DAG转化成二分图：将一个点拆分成两个点：入点和出点，如果A，B之间有边，就把A的出点和B的入点相连。
RT↓
这张图建完转成二分图是这个样子（且已经匹配完
匹配完了就是这个样子：
三种颜色即代表了三条路径
可以这样想：如果图不连通，最小路径覆盖即为点数，每多一次匹配，会多覆盖一个点，最小路径数-1。又因为每个点只能用一次，所以最小路径覆盖 = 原图上的点数 - 最大匹配数 。
\(End\)
大概是写的最后一篇博客了吧QAQ。