题解 P6577 【【模板】二分图最大权完美匹配】

George1123

2020-05-28 19:53:01

Solution

## KM 算法 [$\Huge\color{#f0e046}\tt My~Cnblogs$](https://www.cnblogs.com/Wendigo/p/12983311.html) 可能需要先去学学匈牙利算法等二分图相关知识。 --- > [模板题-洛谷P6577 【模板】二分图最大权完美匹配](https://www.luogu.com.cn/problem/P6577) > 给 $n$ 和 $m$ 与边 $u_i,v_i,w_i(1\le i\le m)$。有一个二分图,两边各 $n$ 个点,共 $m$ 条边,保证有完美匹配,求完美匹配最大边权之和。 > 数据范围:$1\le n\le 500$,$1\le m\le \frac{n\times (n-1)}{2}$,$-19980731\le w_i \le 19980731$,无重边。 --- 卡网络流以及一切复杂度 $> \Theta(n^3)$ 的算法,卡不掉怪良心出题人。 --- - **奇奇怪怪的定义** **顶标**:两边点都有的标记(左 $a_i$ 右 $b_j$)满足 $a_i+b_j\ge w_{i,j}$,不唯一。 **相等边**:$a_i+b_j=w_{i,j}$ 的边 $(i,j)$。 **相等子图**:相等边构成的子图。 **交错树**:增广路径形成的树。 > $\tt KM$ 算法的结论:$\color{#f00}{\texttt{当每个相等子图完备匹配时,二分图得到最大匹配。}}$ 因为显然,因为这个时候不可能有比它更优的匹配。 --- - **奇奇怪怪的算法** 很明显,**并不是所有** 的顶标分配方案都能使“每个相等子图完备匹配”的。 但是,**找到一个可行的** 顶标分配方案是很简单的,所以可以找到一种顶标分配然后找增广路的同时调整。 然后在发现相等子图的完备匹配后就匹配。 **具体流程:** $(1)$ 分配可行顶标,并对每个节点执行 $(2),(3),(4)$。 $(2)$ **匈牙利算法**找增广。 $(3)$ 找不到增广路(相等子图匹配)就调整顶标。 $(4)$ 重复 $(2),(3)$ 直到找到增广路。 --- - **代码** 分析一下代码可知**实际时间复杂度** $\Theta(n^4)$。 ```cpp //Data const ll N=500; ll n,m,e[N+7][N+7]; //KM ll mat[N+7],d[N+7],va[N+7],vb[N+7],ak[N+7],bk[N+7]; ll Dfs(ll u){ va[u]=1; for(ll v=1;v<=n;v++)if(!vb[v]){ if(ak[u]+bk[v]-e[u][v]==0){ vb[v]=1; if(!mat[v]||Dfs(mat[v])) return mat[v]=u,1; } else d[v]=min(d[v],ak[u]+bk[v]-e[u][v]); } return 0; } ll KM(){ fill(ak+1,ak+n+1,-INF); for(ll u=1;u<=n;u++) for(ll v=1;v<=n;v++) ak[u]=max(ak[u],e[u][v]); for(ll u=1;u<=n;u++){ while(true){ fill(va+1,va+n+1,0); fill(vb+1,vb+n+1,0); fill(d+1,d+n+1,INF); if(Dfs(u)) break; ll c=INF; for(ll v=1;v<=n;v++)if(!vb[v]) c=min(c,d[v]); for(ll v=1;v<=n;v++)if(va[v]) ak[v]-=c; for(ll v=1;v<=n;v++)if(vb[v]) bk[v]+=c; } } ll res=0; for(ll v=1;v<=n;v++) res+=e[mat[v]][v]; return res; } //Main int main(){ scanf("%lld%lld",&n,&m); for(ll u=1;u<=n;u++) for(ll v=1;v<=n;v++) e[u][v]=-INF; for(ll i=1;i<=m;i++){ ll u,v,w; scanf("%lld%lld%lld",&u,&v,&w); e[u][v]=max(e[u][v],w); } printf("%lld\n",KM()); for(ll u=1;u<=n;u++) printf("%lld ",mat[u]);puts(""); return 0; } ``` --- 这时候可以得 $50$ 分,剩余的 $\tt TLE$。 > **废话**:不得不佩服出题人!大部分人的 $\tt KM$ 算法都是上面这么写的,要知道还有 $\Theta(n^3)$ 的 $\tt KM$,得找遍全网吧!我找了一个下午终于找到了,希望写了这篇文章后,大家就不需要像我这么累了! --- - **奇奇怪怪的优化** 就是把 $\tt Dfs$ 换成 $\tt Bfs$。本质和上面代码是一样的。 每个左边的点只会进队、搜索一次。$\tt p$ 数组记录的是增广交错树。 这个 $\tt Bfs$ 是迭代写的,所以不需要 $\tt queue$。 --- - **代码** 随机数据下是 $\Theta(n^3)$,听说可以卡成 $\Theta(n^4)$。但是这样卡貌似没意义。 ```cpp //Data const int N=500; int n,m,e[N+7][N+7]; //KM int mb[N+7],vb[N+7],ka[N+7],kb[N+7],p[N+7],c[N+7]; int qf,qb,q[N+7]; void Bfs(int u){ int a,v=0,vl=0,d; for(int i=1;i<=n;i++) p[i]=0,c[i]=inf; mb[v]=u; do { a=mb[v],d=inf,vb[v]=1; for(int b=1;b<=n;b++)if(!vb[b]){ if(c[b]>ka[a]+kb[b]-e[a][b]) c[b]=ka[a]+kb[b]-e[a][b],p[b]=v; if(c[b]<d) d=c[b],vl=b; } for(int b=0;b<=n;b++) if(vb[b]) ka[mb[b]]-=d,kb[b]+=d; else c[b]-=d; v=vl; } while(mb[v]); while(v) mb[v]=mb[p[v]],v=p[v]; } ll KM(){ for(int i=1;i<=n;i++) mb[i]=ka[i]=kb[i]=0; for(int a=1;a<=n;a++){ for(int b=1;b<=n;b++) vb[b]=0; Bfs(a); } ll res=0; for(int b=1;b<=n;b++) res+=e[mb[b]][b]; return res; } //Main int main(){ n=ri,m=ri; for(int a=1;a<=n;a++) for(int b=1;b<=n;b++) e[a][b]=-inf; for(int i=1;i<=m;i++){ int u=ri,v=ri,w=ri; e[u][v]=max(e[u][v],w); } printf("%lld\n",KM()); for(int u=1;u<=n;u++) printf("%d ",mb[u]);puts(""); return 0; } ``` --- 是不是看起来特别玄学?$\tt KM$ 这种偏僻又难懂的算法,或许还是背板子好。 对了,然后就能 $\tt AC$ 了。 --- **祝大家学习愉快!**