设二分图的两部分点集分别为 $X=\{X_1, X_2, \ldots, X_n\}$ 和 $Y=\{Y_1, Y_2, \ldots, Y_m\}$, $\left<X_i, Y_j\right>$ 的边权为 $w_{ij}$.
给两部分点集分别赋点权 $\{A_i\}, \{B_i\}$, 使得 $A_i+B_j \ge w_{ij}$. 取等的边的生成子图叫做相等子图。那么相等子图的完美匹配就是最大权匹配。我们需要适当选取权值，使相等子图有完美匹配。
算法流程如下：
KM算法需要对每回修改后的子图重新搜索交错路，时间复杂度可达 $O(n^4)$.
由于原交错树仍然是可用的，我们考虑不重新搜索交错路，而是在原交错树上直接扩展新边。
具体地，我们在加入 $X_k$ 的过程中，由 $X_k$ 开始扩展交错树。
对于每个 $Y'$ 中的点，记录它的父结点；对于 $Y_j \in Y \setminus Y'$, 我们维护 $slack_j=\min\{A_i+B_j-w_{ij}\ \mid X_i \in X'\}$, 取得最小值的 $X_i$ 是它的准父结点（有多个任取一个）。
扩展的流程是：
在实现上，我们记 $match_j$ 表示 $Y_j$ 的匹配点，$pre_j$ 表示 $Y_j$ 的（准）父结点的匹配点，不存在记为 $0$.
示例：假设 $n=m \le 500$, 所有边权和答案绝对值小于 $10^{18}$. 输入 $n$ 和边权，输出 $Y_j$ 的匹配点。
1 #include <bits/stdc++.h> 2 const int N=501; 3 int n, match[N]; 4 bool vis[N]; 5 long long f[N][N], a[N], b[N], slack[N], pre[N]; 6 template<class T1, class T2> bool cmin(T1 &a, const T2 &b) 7 { 8 return b<a?(a=b, true):false; 9 } 10 template<class T1, class T2> bool cmax(T1 &a, const T2 &b) 11 { 12 return a<b?(a=b, true):false; 13 } 14 int main() 15 { 16 scanf("%d", &n); 17 for(int i=1; i<=n; ++i) { 18 for(int j=1; j<=n; ++j) 19 scanf("%d", f[i]+j); 20 a[i]=*std::max_element(f[i]+1, f[i]+n+1); 21 } 22 for(int i=1; i<=n; ++i) { 23 int x=0, cho; 24 memset(vis+1, 0, n); 25 memset(pre+1, 0, n*sizeof(int)); 26 memset(slack+1, 63, n*sizeof(long long)); 27 match[0]=i; 28 do { 29 int u=match[x]; 30 long long min=1e18; 31 vis[x]=true; 32 for(int v=1; v<=n; ++v) { 33 if(!vis[v]) { 34 long long t=a[u]+b[v]-f[u][v]; 35 if(cmin(slack[v], t)) 36 pre[v]=x; 37 if(cmin(min, slack[v])) 38 cho=v; 39 } 40 } 41 for(int j=0; j<=n; ++j) { 42 if(vis[j]) { 43 a[match[j]]-=min; 44 b[j]+=min; 45 } else 46 slack[j]-=min; 47 } 48 x=cho; 49 } while(match[x]); 50 while(x) { 51 match[x]=match[pre[x]]; 52 x=pre[x]; 53 } 54 } 55 for(int i=1; i<=n; ++i) 56 printf("%d%c", match[i], " \n"[i==n]); 57 return 0; 58 }
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。