匈牙利算法和KM算法的总结/扩展阅读
匈牙利算法
Problem
Solution
二分图不一定为无向图，只需边的两端的点可分即是二分图。这是最小边覆盖的前提条件。
匈牙利算法匹配流程：
- 确定二分图的两个点集，选择一个点集作为搜索起点。设为左边点。
- 两个数组：match, check。match 代表匹配点，check 代表一次深搜的 vis（是否被遍历）。match 建议初始化为 -1。
枚举每个左边点。如果左边点没有被匹配过（match 为 -1），进行深搜匹配。最大匹配不会超过左边点的个数，因此每次深搜最多只增加一对匹配。
I. 枚举相邻的右点。如果没有被匹配过则直接返回，因为已经增加一对匹配。如果被匹配过了则深搜到右点的匹配点，看看是否有点没被匹配，持续下去。必须找到一个没被匹配的右点，才能形成增广路。
II. 若找到没被匹配过的点或深搜的点返回了 true，更新匹配，返回 true。代表这是一个增广路。
III. 若啥也没找到返回 false。代表找不到增广路。
- 若深搜左边点返回 ture，答案计数 +1. 代表找到了增广路。
Codes
#include<bits/stdc++.h>
using namespace std;
const int N=2010,M=8e6+10;
int h[N],to[M],nexp[M],p=1;
inline void ins(int a,int b){
nexp[p]=h[a],h[a]=p,to[p]=b,p++;
}
bool check[N];
int match[N];
bool dfs(int x){
for(int u=h[x];u;u=nexp[u]){
if( !check[to[u]] ){
check[to[u]]=1;
if( match[to[u]]==-1 || dfs(match[to[u]]) ){
match[to[u]]=x;
match[x]=to[u];
return true;
}
}
}
return false;
}
int main(){
ios::sync_with_stdio(false);
int n,m,e;
cin>>n>>m>>e;
int u,v;
for(int i=0;i<e;i++){
cin>>u>>v;
if(v>m) continue;
v+=n;
ins(u,v),ins(v,u);
}
memset(match,-1,sizeof(match));
int ans=0;
for(int i=1;i<=n;i++){
if(match[i]==-1){
memset(check,0,sizeof(check));
if(dfs(i)) ans++;
}
}
cout<<ans<<endl;
return 0;
}扩展阅读
Renfei Song's Blog - 二分图的最大匹配、完美匹配和匈牙利算法
KM 算法 - 带权二分图最佳匹配
前提，二分图左侧端点数 <= 右侧端点数
-1、说明
为了方便记忆和记录使用了大量看上去令人很害怕的数学符号。虽然基本算是乱用。
以及只讲了怎么做没讲为什么，也没说如何理解。
所以建议在理解的情况下再按下方的描述进行记忆 / 加深理解流程。
实际上以下应该只算是笔记 2333
如果想学习 KM 算法，请直接翻至最下方的扩展阅读。
0、概括
其实就是匈牙利算法的扩展。同时引入了 相等子图 以及 顶标 等概念。
在这里我们称顶标为 期望 。
1、数组的初始化
check 标记：每次深搜的遍历情况
match 匹配：右侧端点匹配的点
以上数组与匈牙利算法基本相同。下面为新引入的数组：
ex 期望：每个点的期望值
slack 最小期望差：左侧端点 ex 减少 slack 可使相等子图增加至少一个右侧点。
2、完备匹配
左侧点 / 右侧点至少有一边全部匹配，则称此匹配为完备匹配。
3、最佳匹配
带权二分图中权值和最大的完备匹配称为最佳匹配。
最佳匹配不等于最大权匹配。
4、相等子图 - $G'$
令左侧为 X 侧，右侧为 Y 侧。
则 $ex_{x_{i}}+ex_{y_j}=w (x_i , y_j)$ 的边 $(X_i,Y_j)$ 存在于 $G'$ 中。
5、流程
初始化 $ex_{x_i}=max(w(x_i,y_j))\ ,\ ex_{y_i}=0$ 。
针对每个 $X_i$ 在 $G'$ 中寻找增广路。
每次寻找增广路过程中， $slack=INF$ 。
若不存在增广路，则形成由许多交错路构成的交错树 $T$ 。在寻找增广路过程中，针对 $x_i \in T,\ y_j \notin G',\ (x_i,y_j) \in G$ ，更新 $slack=min(slack,\ w(x_i,y_j))$ 。
则针对每个 $x_i,y_j \in T,\ ex_{x_i}-=slack,\ ex_{y_j}+=slack$ 。
若 $x_i \in T,\ y_j \notin G'$，则 $ex_{x_{i}}+ex_{y_j}$ 减小，说明边 $(x_i, y_j)$ 可能加入 $G'$。
而 $slack$ 的取值尽量只让 $G'$ 扩充一条边。
扩充 $G'$ 之后，重复寻找增广路。
每个 $x_i$ 都找到增广路之后，则形成最佳匹配。
扩展阅读 / 引用文章
KM 算法详解 + 模板 - 段文弱
上面这篇个人认为讲的很有趣，很好理解。但代码相较下方文章稍显冗长。
KM 算法 - C20180630_zjf
本文叙述的大部分概念都引自上文。实际上本文只是上文的精简版。代码精简好背，而且也比较好理解。
练习题目
Luogu P1559 运动员最佳匹配问题
KM 算法模板题。
Codes:
#include<bits/stdc++.h>
#define INF (0x7fffffff)
using namespace std;
const int N=25;
int w[N][N];
int match[N];
int vis_l[N];
int vis_r[N];
int ex_l[N];
int ex_r[N];
int slack;
int n;
bool dfs(int x){
vis_l[x]=1;
int gap;
for(int i=1;i<=n;i++){
if(vis_r[i]) continue;
gap=ex_l[x]+ex_r[i]-w[x][i];
if(gap==0) {
vis_r[i]=1;
if(match[i]==-1 || dfs(match[i])){
match[i]=x;
return true;
}
}
else if(gap>0)slack=min(slack,gap);
}
return false;
}
inline int KM(){
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
ex_l[i]=max(ex_l[i],w[i][j]);
memset(match,-1,sizeof(match));
for(int i=1;i<=n;i++){
while(1){
slack=INF;
memset(vis_l,0,sizeof(vis_l));
memset(vis_r,0,sizeof(vis_r));
if(dfs(i)) break;
for(int i=1;i<=n;i++){
if(vis_l[i]) ex_l[i]-=slack;
if(vis_r[i]) ex_r[i]+=slack;
}
}
}
int ret=0;
for(int i=1;i<=n;i++)
ret+=w[match[i]][i];
return ret;
}
int main(){
ios::sync_with_stdio(false);
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cin>>w[i][j];
int na;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
cin>>na;
w[j][i]*=na;
}
cout<<KM()<<endl;
return 0;
}
本文链接：https://pst.iorinn.moe/archives/Bipartite_Graph_matching_problem.html
许可： https://pst.iorinn.moe/license.html若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆