【模板】最小割树（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！

相关文章