最小割树

知识点

定理：

无向图任意两点间的最小割，不同的只有(n-1)个。

实现：
1.在点集中任取两点(S,T)，求最最小割(C)，在最小割树中加入边(S,T,|C|)。

2.把点集分为与(S)联通的集合和不与(S)联通的集合，递归进行操作(1)，直至点集大小为(1)时停止。

题目

【ZJOI2011】最小割

【2011福建】交通查询系统

【CQOI2016】不同的最小割

//【CQOI2016】不同的最小割 代码
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdio>
#include<iomanip>
#include<cstdlib>
#include<set>
#define MAXN 0x7fffffff
typedef long long LL;
const int N=1005,M=8505;
using namespace std;
inline int Getint(){register int x=0,f=1;register char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}return x*f;}
int n,m,id[N];
set<int>ans;
namespace GHT{
	int h[N],cnt;
	struct node{int to,next,flow,pair;}g[M<<2];
	void AddEdge(int x,int y,int z){
		g[++cnt].to=y,g[cnt].next=h[x],h[x]=cnt,g[cnt].flow=z,g[cnt].pair=cnt+1;
		g[++cnt].to=x,g[cnt].next=h[y],h[y]=cnt,g[cnt].flow=z,g[cnt].pair=cnt-1;
	}
	
	int S,T;
	int dis[N],GAP[N],col[N];
	void Init(){
		static int q[N];
		fill(dis+1,dis+1+n,0),fill(GAP+1,GAP+1+n,0);
		int l=0,r=1;q[++l]=T,++GAP[dis[T]=1];
		while(l<=r){
			int x=q[l++];
			for(int i=h[x];i;i=g[i].next){
				int to=g[i].to;
				if(!dis[to])++GAP[dis[to]=dis[x]+1],q[++r]=to; 
			}
		}
	}
	int Dfs(int x,int Maxf){
		if(x==T||!Maxf)return Maxf;
		int ret=0;
		for(int i=h[x];i;i=g[i].next){
			int to=g[i].to;
			if(g[i].flow&&dis[x]==dis[to]+1){
				int dlt=Dfs(to,min(g[i].flow,Maxf-ret));
				g[i].flow-=dlt,g[g[i].pair].flow+=dlt;
				ret+=dlt;if(dis[S]==n+1||ret==Maxf)return ret;
			}
		}
		if(!(--GAP[dis[x]]))dis[S]=n+1;
		else ++GAP[++dis[x]];
		return ret;
	}
	int SAP(){
		Init();
		int ans=Dfs(S,MAXN);
		while(dis[S]<=n)ans+=Dfs(S,MAXN);
		return ans;
	}
	void Paint(int x){
		col[x]=1;
		for(int i=h[x];i;i=g[i].next)
			if(g[i].flow&&!col[g[i].to])Paint(g[i].to);
	} 
	void Build(int l,int r){
		if(l==r)return;
		for(int i=1;i<=cnt;i+=2)g[i].flow=g[i+1].flow=(g[i].flow+g[i+1].flow)>>1;
		S=id[l],T=id[r];
		ans.insert(SAP());
		fill(col+1,col+1+n,0),Paint(S);
		static int tmp[N];
		int L=l,R=r;
		for(int i=l;i<=r;i++){
			if(col[id[i]])tmp[L++]=id[i];
			else tmp[R--]=id[i];
		}
		for(int i=l;i<=r;i++)id[i]=tmp[i];
		Build(l,L-1),Build(R+1,r);
	}
}
int main(){
	n=Getint(),m=Getint();
	for(int i=1;i<=m;i++){
		int x=Getint(),y=Getint(),z=Getint();
		GHT::AddEdge(x,y,z);
	}
	for(int i=1;i<=n;i++)id[i]=i;random_shuffle(id+1,id+1+n);
	GHT::Build(1,n);
	cout<<ans.size();
	return 0;
}