最大流/最小割树/等价流树 学习笔记
最小割树 ( ext{Gomory-Hu Tree})
前置
约定无向图点数为(n)，边数为(m)
割:断开一些边，使得(s,t)两点不连通
设(lambda(u,v))为(u,v)的最小割权值
在非负边权的无向图上使用网络流即可求得两点间的最小割，但是如果涉及查询所有点对的最小割，就需要进行(n^2)次网络流，复杂度很高
简介
对于非负边权的无向图，适用于求出多点对之间的最小割/最大流的结构
1.( ext{Gomory-Hu Tree})的核心性质
构造树，使得树边((u,v))满足割掉这条边后，(u,v)的最小割对应将图分为树在两边的这两个集合
而边((u,v))的权值(w(u,v)=lambda(u,v))
2.求解最小割的方法
引理:
(lambda(a,b)ge min{lambda(a,c),lambda(c,b)})
假设(lambda(a,b) < min{lambda(a,c),lambda(c,b)})
设(a,b)最小割的两个集合后两点所属的联通块集合为(A,B)
1.若(cin A)，则(a,b)最小割也是(b,c)的割
2.若(cin B)，则(a,b)最小割也是(a,c)的割
以上两种情况均与(lambda(a,b) < min{lambda(a,c),lambda(c,b)})矛盾
假设要求(u,v)两点间的最短路，则答案就是(u,v)在树上路径的最小边权值，设其为边((s,t))
由上面的引理，显然有(lambda(u,v)gelambda(s,t))
而我们由( ext{Gomory-Hu Tree})的性质知道，(s,t)的割也是(u,v)的一个割，即(lambda(u,v)le lambda(s,t))
所以答案就是(lambda(s,t))
构建方法
构建( ext{Gomory-Hu Tree})最重要的一条引理，可以认为是最小割的"不交叉"性质
对于(s,t)最小割的一侧，设其点集为(W)，则对于任意的(u,vin W)，存在一个(s,t)最小割(X)，满足(Xsube W)
具体的证明比较复杂，咕，但是这个性质确实非常巧妙
利用这个性质，可以得到( ext{Gomory-Hu Tree})的不严谨的递归构造方法
1.对于当前点集(S)，若(|S|=1)，则结束递归
2.从(S)中选择两个点(x,y)求出最小割，设在割中(x,y)所属点集分别为(X,Y)
3.在( ext{Gomory-Hu Tree})上加入边((x,y,lambda(x,y)))，递归解决子问题(Xcap S,Ycap S)
实际在递归求解(S)的问题时，应该将图中其他的点缩点(这是论文里说的，实际没有人这么写)
是不是不缩点跑出来的树形是错的?
递归求解的次数为(O(n))，只需要求(O(n))次网络流即可
放一下丑陋的板子
#include<bits/stdc++.h>
using namespace std;
typedef pair <int,int> Pii;
#define pb push_back
#define mp make_pair
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
template <class T> inline void cmin(T &a,T b){ ((a>b)&&(a=b)); }
template <class T> inline void cmax(T &a,T b){ ((a<b)&&(a=b)); }
char IO;
template <class T=int> T rd(){
T s=0; int f=0;
while(!isdigit(IO=getchar())) if(IO=='-') f=1;
do s=(s<<1)+(s<<3)+(IO^'0');
while(isdigit(IO=getchar()));
return f?-s:s;
}
const int N=510,M=6200,INF=1e9+10;
int n,m;
int U[M],V[M],W[M];
struct Edge{
int to,nxt,w;
} e[M];
int head[N],ecnt;
void AddEdge(int u,int v,int w) {
e[++ecnt]=(Edge){v,head[u],w};
head[u]=ecnt;
}
void Link(int u,int v,int w){ AddEdge(u,v,w),AddEdge(v,u,w); }
#define erep(u,i) for(int i=head[u];i;i=e[i].nxt)
int dis[N],vc,S,T;
void clear(){ rep(i,1,vc) head[i]=0; ecnt=1,vc=0; }
int Bfs() {
rep(i,1,vc) dis[i]=INF;
static queue <int> que;
dis[S]=0,que.push(S);
while(!que.empty()) {
int u=que.front(); que.pop();
erep(u,i) {
int v=e[i].to,w=e[i].w;
if(!w || dis[v]<=dis[u]+1) continue;
dis[v]=dis[u]+1,que.push(v);
}
}
return dis[T]<INF;
}
int Dfs(int u,int in) {
if(u==T) return in;
int out=0;
erep(u,i) {
int v=e[i].to,w=e[i].w;
if(!w || dis[v]!=dis[u]+1) continue;
int t=Dfs(v,min(in-out,w));
e[i].w-=t,e[i^1].w+=t,out+=t;
if(in==out) break;
}
if(!out) dis[u]=0;
return out;
}
int Dinic(){
int ans=0;
while(Bfs()) ans+=Dfs(S,INF);
return ans;
}
int Mincut(int u,int v){
clear(),vc=n,S=u,T=v;
rep(i,1,m) Link(U[i],V[i],W[i]);
return Dinic();
}
vector <Pii> G[N];
int P[N],R[N];
void Build(int l,int r) {
if(l==r) return;
int x=P[l],y=P[l+1];
int w=Mincut(x,y);
int p1=l-1,p2=r+1;
rep(i,l,r) if(dis[P[i]]<INF) R[++p1]=P[i];
else R[--p2]=P[i];
rep(i,l,r) P[i]=R[i];
G[x].pb(mp(y,w)),G[y].pb(mp(x,w));
Build(l,p1),Build(p2,r);
}
int fa[N][10],s[N][10],dep[N];
void dfs(int u,int f) {
for(int i=1;(1<<i)<=dep[u];++i) fa[u][i]=fa[fa[u][i-1]][i-1],s[u][i]=min(s[u][i-1],s[fa[u][i-1]][i-1]);
for(Pii t:G[u]) if(t.first!=f) {
int v=t.first,w=t.second;
fa[v][0]=u,s[v][0]=w,dep[v]=dep[u]+1;
dfs(v,u);
}
}
int LCA(int x,int y){
if(dep[x]<dep[y]) swap(x,y);
int mi=1e9;
for(int i=0,del=dep[x]-dep[y];(1<<i)<=del;++i) if(del&(1<<i)) cmin(mi,s[x][i]),x=fa[x][i];
if(x==y) return mi;
drep(i,9,0) if(fa[x][i]!=fa[y][i]) cmin(mi,s[x][i]),cmin(mi,s[y][i]),x=fa[x][i],y=fa[y][i];
cmin(mi,s[x][0]),cmin(mi,s[y][0]);
return mi;
}
int main() {
n=rd()+1,m=rd();
rep(i,1,m) U[i]=rd()+1,V[i]=rd()+1,W[i]=rd();
rep(i,1,n) P[i]=i; Build(1,n);
dfs(1,0);
rep(kase,1,rd()) printf("%d
",LCA(rd()+1,rd()+1));//printf("%d
",MinCut(rd()+1,rd()+1));
}
等价流树
等价流树的树形不需要满足( ext{Gomory-Hu Tree})的性质，只需要能够查询两点间的答案即可
在论文中看到的等价流树的非递归构建方法(伪代码)
(w_{1,..,n}=0,fa_{1}=1,fa_{2,..,n}=1)
( ext{for u = 2 to n do})
(v = fa_u)
求解(u,v)最小割
(w_u=lambda(u,v))
( ext{for x=u+1 to n do})
( ext{if} fa_x=v ext{ and x在u这一侧 then }fa_x=u)
( ext{end for})
( ext{end for})
但是这个东西实际也不会跑得比( ext{Gomory-Hu Tree})快，了解一下即可
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef pair <int,int> Pii;
#define reg register
#define pb push_back
#define mp make_pair
#define Mod1(x) ((x>=P)&&(x-=P))
#define Mod2(x) ((x<0)&&(x+=P))
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
template <class T> inline void cmin(T &a,T b){ ((a>b)&&(a=b)); }
template <class T> inline void cmax(T &a,T b){ ((a<b)&&(a=b)); }
char IO;
template <class T=int> T rd(){
T s=0; int f=0;
while(!isdigit(IO=getchar())) if(IO=='-') f=1;
do s=(s<<1)+(s<<3)+(IO^'0');
while(isdigit(IO=getchar()));
return f?-s:s;
}
const int N=860,M=170010,INF=1e9+10;
int n,m;
int U[M],V[M],W[M];
struct Edge{
int to,nxt,w;
} e[M];
int head[N],ecnt;
void AddEdge(int u,int v,int w) {
e[++ecnt]=(Edge){v,head[u],w};
head[u]=ecnt;
}
void Link(int u,int v,int w){ AddEdge(u,v,w),AddEdge(v,u,w); }
#define erep(u,i) for(int i=head[u];i;i=e[i].nxt)
int dis[N],vc,S,T;
void clear(){ rep(i,1,vc) head[i]=0; ecnt=1,vc=0; }
int Bfs() {
rep(i,1,vc) dis[i]=INF;
static queue <int> que;
dis[S]=0,que.push(S);
while(!que.empty()) {
int u=que.front(); que.pop();
erep(u,i) {
int v=e[i].to,w=e[i].w;
if(!w || dis[v]<=dis[u]+1) continue;
dis[v]=dis[u]+1,que.push(v);
}
}
return dis[T]<INF;
}
int Dfs(int u,int in) {
if(u==T) return in;
int out=0;
erep(u,i) {
int v=e[i].to,w=e[i].w;
if(!w || dis[v]!=dis[u]+1) continue;
int t=Dfs(v,min(in-out,w));
e[i].w-=t,e[i^1].w+=t,out+=t;
if(in==out) break;
}
if(!out) dis[u]=0;
return out;
}
int Dinic(){
int ans=0;
while(Bfs()) ans+=Dfs(S,INF);
return ans;
}
int Mincut(int u,int v){
clear(),vc=n,S=u,T=v;
rep(i,1,m) Link(U[i],V[i],W[i]);
return Dinic();
}
int fa[N],w[N];
int main() {
n=rd(),m=rd();
rep(i,1,m) U[i]=rd(),V[i]=rd(),W[i]=rd();
rep(i,2,n) fa[i]=1;
rep(u,2,n) {
int v=fa[u]; w[u]=Mincut(v,u);
rep(x,u+1,n) if(fa[x]==v && dis[x]==INF) fa[x]=u;
}
}