最小割树（GHT）学习笔记

最小割树，顾名思义，就是用来快速求出两点之间最小割的一种树。

经典例题

不难发现，求出两点之间的最小割为 $val$ 后，整个图会被分成互不连通的两部分，不妨使用集合 $A$ 和集合 $B$ 表示。不难发现，对于所有 $x\in A,y\in B$ ，都有 $\operatorname{mincut}(x,y)\le val$ （ $\forall x\in A,y\in B,\exists \operatorname{mincut}(x,y)\le val$ ）。

根据这条性质，我们便可以画一个这样的图：

接下来，我们可以再细分下去：

然后继续细分：

这样，我们就造出了一棵树。不难发现，树上 $x,y$ 两点之间的路径上的最小边权和便是 $\operatorname{mincut}(x,y)$ ，用倍增即可实现 $O(\log n)$ 最小割查询。

完整代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>

using namespace std;

#define S 100005
#define MS 1005

int n,m,q,s,t;
int ineu[S],inev[S],inew[S];
int esum,to[S],c[S],nxt[S],h[MS];
int dep[MS],cur[MS];
int esum2,to2[S],c2[S],nxt2[S],h2[MS];
int nd[MS],tot1,tmp1[MS],tot2,tmp2[MS];
int depp[MS],up[MS][30],minn[MS][30];

inline void init()
{
	esum=1;
	memset(h,0,sizeof(h));
}

inline void add(int x,int y,int w)
{
	to[++esum]=y;
	c[esum]=w;
	nxt[esum]=h[x];
	h[x]=esum;
}

inline void add2(int x,int y,int w)
{
	to2[++esum2]=y;
	c2[esum2]=w;
	nxt2[esum2]=h2[x];
	h2[x]=esum2;
}

inline bool bfs()
{
	memset(dep,0,sizeof(dep));
	queue<int> q;
	q.push(s);
	dep[s]=1;
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(int i=h[u];i;i=nxt[i])
		{
			int v=to[i];
			if(c[i]>0&&dep[v]==0)
			{
				dep[v]=dep[u]+1;
				q.push(v);
			}
		}
	}
	return dep[t]>0;
}

int dfs(int u,int w)
{
	if(u==t)
	{
		return w;
	}
	int sum=0;
	for(int &i=cur[u];i;i=nxt[i])
	{
		int v=to[i];
		if(c[i]>0&&dep[v]==dep[u]+1)
		{
			int re=dfs(v,min(w,c[i]));
			c[i]-=re;
			c[i^1]+=re;
			w-=re;
			sum+=re;
			if(w==0)
			{
				break;
			}
		}
	}
	return sum;
}

inline int dinic()
{
	int ans=0;
	while(bfs())
	{
		for(int i=1;i<=n;i++)
		{
			cur[i]=h[i];
		}
		ans+=dfs(s,1e8);
	}
	return ans;
}

inline int slove(int x,int y)
{
	init();
	s=x;
	t=y;
	for(int i=1;i<=m;i++)
	{
		add(ineu[i],inev[i],inew[i]);
		add(inev[i],ineu[i],0);
		add(inev[i],ineu[i],inew[i]);
		add(ineu[i],inev[i],0);
	}
	return dinic();
}

void built(int l,int r)
{
	if(l==r)
	{
		return; 
	}
	int nans=slove(nd[l],nd[r]);
	add2(nd[l],nd[r],nans);
	add2(nd[r],nd[l],nans);
	tot1=0;
	tot2=0;
	for(int i=l;i<=r;i++)
	{
		if(dep[nd[i]]>0)
		{
			tmp1[++tot1]=nd[i];
		}
		else
		{
			tmp2[++tot2]=nd[i];
		}
	}
	for(int i=1;i<=tot1;i++)
	{
		nd[l+i-1]=tmp1[i];
	}
	for(int i=1;i<=tot2;i++)
	{
		nd[l+tot1-1+i]=tmp2[i];
	}
	int l1=l,r1=l+tot1-1;
	int l2=l+tot1,r2=r;
	built(l1,r1);
	built(l2,r2);
}

void initque(int u,int fa,int val)
{
	depp[u]=depp[fa]+1;
	up[u][0]=fa;
	minn[u][0]=val;
	for(int i=1;i<=25;i++)
	{
		up[u][i]=up[up[u][i-1]][i-1];
		if(up[u][i]!=0)
		{
			minn[u][i]=min(minn[u][i-1],minn[up[u][i-1]][i-1]);
		}
	}
	for(int i=h2[u];i;i=nxt2[i])
	{
		int v=to2[i];
		if(v==fa)
		{
			continue;
		}
		initque(v,u,c2[i]);
	}
}

inline int quemin(int x,int y)
{
	if(depp[x]<depp[y])
	{
		int t=x;
		x=y;
		y=t;
	}
	int res=1e8;
	for(int i=25;i>=0;i--)
	{
		if(depp[up[x][i]]>=depp[y])
		{
			res=min(res,minn[x][i]);
			x=up[x][i]; 
		}
	}
	if(x==y)
	{
		return res;
	}
	for(int i=25;i>=0;i--)
	{
		if(up[x][i]!=up[y][i])
		{
			res=min(res,min(minn[x][i],minn[y][i]));
			x=up[x][i];
			y=up[y][i];
		}
	}
	res=min(res,min(minn[x][0],minn[y][0]));
	return res;
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&ineu[i],&inev[i],&inew[i]);
	}
	for(int i=1;i<=n;i++)
	{
		nd[i]=i;
	}
	built(1,n);
	initque(1,0,0);
	scanf("%d",&q);
	while(q--)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		printf("%d\n",quemin(x,y));
	}
	return 0;
}