有点神奇的东西？但是好像除了板子没什么考点？
给定一张无向联通图，多次询问两点之间的最小割
无向图最小割定义为：删除掉权值和最小的边使得两点之间不联通
网络流这种证明上时不时跟数学挂钩的东西写起来真不容易\(qwq\)
不过也只是证明比较麻烦，理解了以后实现起来和次小生成树难度其实差不多吧（？）
设\(G=(V,E),W? V\)，\(\delta(W)\)为只有一条恰好有一个端点在\(W\)内的边的集合
则我们可以用\(\delta(W)\)来表示一个\(s\in W,t\notin W\)的一个\(s-t\)的割，\(c(W)\)表示\(\sum\limits_{e\in \delta(W)}val(e)\)
\(f(u,v)\)表示\(u,v\)之间的最大流流量（最小割容量）
在一个\(n\)个点的图上，只有\(n-1\)种本质不同的最小割
显然
对于任意\(W? V,c(W)=c(?_VW)\)
证明：真的显然
对于任意\(A? V,B? V\)，有\(c(A)+c(B)\ge c(A∪B)+c(A∩B)\)
证明：如果\(A∩B=\emptyset\)或者\(B\)是\(A\)的子集显然相等
如果\(A,B\)有交且\(B\)不是A$的子集，那么
对于全部类型的边\(a\sim f\)，我们用\(a\)代指边\(a\)的容量
\(c(A)=a+c+e+f,c(B)=b+c+d+f\)
\(c(A)+c(b)=a+b+2c+e+d+2f\)
\(c(A∪B)=a+b+c,c(A∩B)=c+d+e\)
\(c(A∪B)+c(A∩B)=a+b+2c+d+e\)
所以\(c(A)+c(B)\ge c(A∪B)+c(A∩B)\)
定义\(A/B=A∩?_VB\)
对于任意\(A? V,B? V\)，有\(c(A)+c(B)\ge c(A/B)+c(B/A)\)
证明同引理二
假设\(\delta(W)\)是\(s-t\)最小割中\(s\)所在的割集，\(\delta(X)\)是\(u-v\)最小割中\(u\)所在的割集，其中\(u,v\in W\)，那么\(X?W\)
我们一般性地考虑\(u\in X,s\in X\)的情况，其他情况可以通过交换\(u,v\)或者\(X,?_VX\)实现
当\(t\notin X\)：
\(c(X)+c(W)\ge c(X∪W)+c(X∩W)\)
\(c(X∪W)\)是\(s-t\)的一个割，所以\(c(X∪W)\ge c(W)\)
\(c(X∩W)\)是\(u-v\)的一个割，所以\(c(X∩W)\ge c(X)\)
所以\(c(X)=c(X∩W)\)
即\(X?W\)
当\(t\in X\):
根据\(c(X)+c(W)\ge c(X/W)+c(X/W)\)同理证得
然后用数学归纳法可以证明本质不同的最小割只有\(n-1\)种
我们已经知道一个\(n\)个点的无向图上只有\(n-1\)种本质不同的最小割，因此一定存在一棵树，满足树上两点的最小割等于原图中的最小割
最小割树\(T\)满足：如果树上有边\((s,t)\)，那么把边\((s,t)\)去掉后树上产生的两个集合刚好的原图上\((s,t)\)最小割把原图分成的两个集合，且边\((s,t)\)的权值等于图上\((s,t)\)的最小割
原图上\((u,v)\)两点的最小割等于最小割树上\((u,v)\)两点之间的最小割
证明：
对于任意\(p\in V_x,q\in V_y,f(x,y)\ge f(p,q)\)
对于带权图\(G=(V,E)\)，\(f(u,v)\ge min\{f(u,w),f(w,v)\}\)
均由最小割定义证明
那么，若\(p,q\)是最小割树上直接相连的两点，且\(f(p,q)\)为\((x,y)\)在最小割树上的最小割，那么
\(f(x,y) = f(p,q)\)
所以我们只要构造出最小割树然后倍增找最小值就好了
直接按定义构造，每次随意选两个点，然后跑出最小割，将原图分成两个集合，再分治构造
假设每次求最小割复杂度为\(O(n^2m)\)，需要求\(n\)次最小割，加上查询，总复杂度\(O(n^3m+qlogn)\)
实际复杂度远达不到毕竟法律规定网络流题不许卡dinic
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
using namespace std;
namespace red{
#define int long long
#define eps (1e-8)
inline int read()
{
int x=0;char ch,f=1;
for(ch=getchar();(ch<'0'||ch>'9')&&ch!='-';ch=getchar());
if(ch=='-') f=0,ch=getchar();
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return f?x:-x;
}
const int N=5010,inf=0x3f3f3f3f;
int n,m,st,ed;
int id[N],dep[N],lg[N];
int f[N][11],v[N][11];
int head[N],cnt;
struct point
{
int nxt,to,val;
point(){}
point(const int &nxt,const int &to,const int &val):nxt(nxt),to(to),val(val){}
}a[N<<2];
inline void link(int x,int y,int z)
{
a[++cnt]=(point){head[x],y,z};head[x]=cnt;
a[++cnt]=(point){head[y],x,z};head[y]=cnt;
}
namespace ght
{
int col[N],col_bucket[N];
int head[N],cur[N],cnt=1,tot;
struct point
{
int nxt,to,c,f;
point(){}
point(const int &nxt,const int &to,const int &c,const int &f):nxt(nxt),to(to),c(c),f(f){}
}a[N<<2];
inline void link(int x,int y,int z)
{
a[++cnt]=(point){head[x],y,z,0};head[x]=cnt;
a[++cnt]=(point){head[y],x,z,0};head[y]=cnt;
}
int d[N];
queue<int> q;
inline bool bfs()
{
memset(d,0,sizeof(d));
memset(cur,0,sizeof(cur));
q.push(st);d[st]=1;
while(!q.empty())
{
int now=q.front();
q.pop();
cur[now]=head[now];
for(int i=head[now];i;i=a[i].nxt)
{
int t=a[i].to;
if(!d[t]&&a[i].c>a[i].f)
{
d[t]=d[now]+1;
q.push(t);
}
}
}
return d[ed];
}
inline int dfs(int now,int c)
{
if(now==ed||!c) return c;
int ret=c,f;
for(int i=cur[now];i;i=a[i].nxt)
{
cur[now]=i;
int t=a[i].to;
if(d[t]==d[now]+1&&a[i].c>a[i].f)
{
f=dfs(t,min(a[i].c-a[i].f,ret));
a[i].f+=f;
a[i^1].f-=f;
ret-=f;
if(!ret) return c;
}
}
if(ret==c) d[now]=0;
return c-ret;
}
inline int dinic(int x,int y)
{
int ret=0;
st=x,ed=y;
for(int i=1;i<=cnt;++i) a[i].f=0;
while(bfs()) ret+=dfs(st,inf);
return ret;
}
inline void get_color(int now,int color)
{
col[now]=color;
for(int i=head[now];i;i=a[i].nxt)
{
int t=a[i].to;
if(a[i].c>a[i].f&&col[t]!=color) get_color(t,color);
}
}
inline void build(int l,int r)
{
if(l==r) return;
int x=id[l],y=id[l+1];
int cut=dinic(x,y);
get_color(x,++tot);
int tl=l,tr=r;
for(int i=l;i<=r;++i)
if(col[id[i]]==tot) col_bucket[tl++]=id[i];
else col_bucket[tr--]=id[i];
for(int i=l;i<=r;++i) id[i]=col_bucket[i];
red::link(x,y,cut);
build(l,tl-1);
build(tr+1,r);
}
}
inline void dfs(int now,int fa)
{
for(int i=1;i<=10;++i)
{
f[now][i]=f[f[now][i-1]][i-1];
v[now][i]=min(v[now][i-1],v[f[now][i-1]][i-1]);
}
dep[now]=dep[fa]+1;
for(int i=head[now];i;i=a[i].nxt)
{
int t=a[i].to;
if(t==fa) continue;
v[t][0]=a[i].val;
f[t][0]=now;
dfs(t,now);
}
}
inline int query(int x,int y)
{
int ret=inf;
while(dep[x]^dep[y])
{
if(dep[x]<dep[y]) swap(x,y);
int d=lg[dep[x]-dep[y]]-1;
ret=min(ret,v[x][d]);
x=f[x][d];
}
if(x==y) return ret;
for(int d=10;~d;--d)
{
if(f[x][d]^f[y][d])
{
ret=min(ret,min(v[x][d],v[y][d]));
x=f[x][d],y=f[y][d];
}
}
ret=min(ret,min(v[x][0],v[y][0]));
return ret;
}
inline void main()
{
n=read(),m=read();
for(int x,y,z,i=1;i<=m;++i)
{
x=read(),y=read(),z=read();
ght::link(x,y,z);
}
for(int i=1;i<=n;++i) id[i]=i,lg[i]=lg[i>>1]+1;
lg[0]=1;
ght::build(1,n);
dfs(1,0);
m=read();
for(int x,y,i=1;i<=m;++i)
{
x=read(),y=read();
printf("%lld\n",query(x,y));
}
}
}
signed main()
{
red::main();
return 0;
}原文：https://www.cnblogs.com/knife-rose/p/12102795.html