【模板】最小割树(Gomory-Hu Tree)

时间:2023-11-28 22:32:20

传送门

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!