匈牙利算法
简介
匈牙利算法是一种求二分图最大匹配的算法.
时间复杂度: 邻接表/前向星: \(O(n * m)\), 邻接矩阵: \(O(n^3)\).
空间复杂度: 邻接表/前向星: \(O(n + m)\), 邻接矩阵: \(O(n^2)\).
它的主要思路就是对每个点寻找增广路, 尝试改变之前的选择, 判断是否可行.
事实上, 利用dinic/isap跑二分图有 \(O(n * \sqrt{m})\) 的优秀复杂度(不会证), 因此匈牙利算法仅用于少数特殊情况↓
代码
int to[nsz][nsz]; //邻接表
int vi[nsz],mat[nsz];
bool arg(int p){
rep(i,1,to[0]){
int v=to[p][i];
if(vi[v])continue;
vi[v]=1;
if(mat[v]==0||arg(mat[v])){
mat[v]=p,mat[p]=v;
return 1;
}
}
return 0;
}
int hung(){
int res=0;
repdo(i,1,n){
memset(vi,0,sizeof(vi));
res+=arg(i);
}
return res;
}
二分图最小字典序匹配
简介
这就是上面说的特殊情况:P
考虑匈牙利算法的过程: 将每一个点尝试增广, 同时改变之前的点的匹配.
因此, 我们可以考虑将所有点的出边按标号排序, 逆向遍历每一个点, 并按标号顺序尝试增广.
显然, 第一个点的匹配一定是它能匹配到的最小标号, 第二个点的匹配是满足第一个点时的最小标号, 以此类推.
代码
//[NOI2009] 变换序列
int to[nsz][3];
int vi[nsz],mat[nsz];
bool arg(int p){
rep(i,0,1){
int v=to[p][i];
if(vi[v])continue;
vi[v]=1;
if(mat[v]==0||arg(mat[v])){
mat[v]=p,mat[p]=v;
return 1;
}
}
return 0;
}
int hung(){
int res=0;
repdo(i,n-1,0){
memset(vi,0,sizeof(vi));
res+=arg(i);
}
return res;
}