【模板】最小割树（Gomory-Hu Tree）

ゝ一纸荒年。 2022-01-09 07:43 180阅读 0赞

## [ 传送门 ][Link 1] ##

## **Description**  ##

> 给定一个\\(n\\)个点\\(m\\)条边的无向连通图，多次询问两点之间的最小割
> 
> 两点间的最小割是这样定义的：原图的每条边有一个割断它的代价，你需要用最小的代价使得这两个点不连通

## **Solution**  ##

> 对于一张无向图，如果 \\(s \\rightarrow t\\) 的最大流是 \\(f\\)，\\(s\\), \\(t\\) 所在的割集为 \\(S\\), \\(T\\)，那么 \\(\\forall\_\{x \\in S, y \\in T\}\\), \\(\\operatorname\{maxflow\}(x \\rightarrow y) = f\\)
> 
> 根据以上性质，我们考虑递归求解
> 
> 构造集合 \\(G\\) 的最小割树：
> 
>  *  任意选两个点，求出最小割，在两个点之间连权值为最小割的边
>  *  对两个割集分别求解
> 
> \\(Wa\\)了数十次
> 
> 以后用`static`的时候还是注意点

## **Code ** ##

#include<bits/stdc++.h> #define ll long long #define reg register #define ri reg int i using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();} return x*f; } const int MN=505,MM=1505,inf=1e9; struct edge{int to,w,nex;}e[MM<<1],E[MN<<1];int cur[MN],Hr[MN],hr[MN],En=1,en=1; void ins(int x,int y,int w,int *h,edge *ed,int &tt) { ed[++tt]=(edge){y,w,h[x]},h[x]=tt; ed[++tt]=(edge){x,w,h[y]},h[y]=tt; } int d[MN],q[MN],top; bool bfs(int S,int T) { memset(d,0,sizeof d); reg int i,j; for(d[q[i=top=1]=S]=1;i<=top;++i) for(j=hr[q[i]];j;j=e[j].nex) if(e[j].w&&!d[e[j].to]) d[q[++top]=e[j].to]=d[q[i]]+1; return d[T]; } int dfs(int x,int T,int f) { if(x==T) return f; int used=0; for(int &i=cur[x];i;i=e[i].nex) if(e[i].w&&d[e[i].to]==d[x]+1) { int tmp=dfs(e[i].to,T,min(f-used,e[i].w)); e[i].w-=tmp,e[i^1].w+=tmp;used+=tmp; if(f==used) return f; } return d[x]=-1,used; } void clear(){for(reg int i=2;i<en;i+=2)e[i].w=e[i^1].w=(e[i].w+e[i^1].w)>>1;} int dinic(int S,int T) { int maxflow=0;clear(); while(bfs(S,T)) { memcpy(cur,hr,sizeof cur); maxflow+=dfs(S,T,inf); } return maxflow; } void Build(int *id, int n) { if(n==1) return; static int s[MN],t[MN];int cnts=0,cntt=0; int cut=dinic(id[0],id[1]); ins(id[0],id[1],cut,Hr,E,En); for(reg int i=0;i<n;++i) if(d[id[i]]) s[cnts++]=id[i]; else t[cntt++]=id[i]; memcpy(id,s,cnts<<2); memcpy(id+cnts,t,cntt<<2); if(cnts) Build(id,cnts); if(cntt) Build(id+cnts,cntt); } int n,dep[MN],fa[MN][15],path[MN][15]; void init_dfs(int x,int f) { for(ri=Hr[x];i;i=E[i].nex)if(E[i].to!=f) dep[E[i].to]=dep[x]+1,fa[E[i].to][0]=x,path[E[i].to][0]=E[i].w,init_dfs(E[i].to,x); } void init() { dep[1]=1;init_dfs(1,-1);reg int i,j; for(i=1;i<10;++i)for(j=1;j<=n;++j) { fa[j][i]=fa[fa[j][i-1]][i-1]; path[j][i]=min(path[j][i-1],path[fa[j][i-1]][i-1]); } } int Min(int x,int y) { reg int ret=1e9; if(dep[x]>dep[y]) std::swap(x,y); reg int i,c=dep[y]-dep[x]; for(i=8;~i;--i) if(c>>i&1) { ret=min(ret,path[y][i]),y=fa[y][i]; } if(x==y) return ret; if(dep[x]!=dep[y]) return -1; for(i=8;~i;--i)if(fa[x][i]!=fa[y][i]) { ret=min(ret,min(path[x][i],path[y][i])),x=fa[x][i],y=fa[y][i]; } return min(ret,min(path[x][0],path[y][0])); } int id[MN]; int main() { reg int i,m,q,x,y; n=read(),m=read(); while(m--) x=read(),y=read(),ins(x,y,read(),hr,e,en); for(i=1;i<=n;++i) id[i-1]=i;Build(id,n);init(); q=read(); while(q--) { x=read();y=read(); printf("%d\n",Min(x,y)); } return 0; }

--------------------

Blog来自**PaperCloud**，未经允许，请勿转载，TKS！

转载于:https://www.cnblogs.com/PaperCloud/p/10674424.html

[Link 1]: https://www.luogu.org/problemnew/show/P4897