最小割树详解[模板]

问题

给

定

n

个

点

m

条

边

的

无

向

图

,

q

个

询

问

,

每

次

询

问

两

个

点

,

求

最

小

割

给定n个点m条边的无向图,q个询问,每次询问两个点,求最小割

给定n个点m条边的无向图,q个询问,每次询问两个点,求最小割

q

<

=

1

e

5

\color{Red}q<=1e5

q<=1e5

两

点

的

最

小

割

跑

一

边

最

大

流

就

好

了

,

因

为

最

大

流

=

=

最

小

割

两点的最小割跑一边最大流就好了,因为最大流==最小割

两点的最小割跑一边最大流就好了,因为最大流==最小割

但是面对这么多的询问,就需要我们的最小割树登场了。

具体做法

首

先

最

小

割

树

是

一

颗

树

,

有

着

这

样

一

个

性

质

首先最小割树是一颗树,有着这样一个性质

首先最小割树是一颗树,有着这样一个性质

对

于

树

中

任

意

两

点

s

和

t

,

s

和

t

在

原

图

的

最

小

割

等

于

最

小

割

树

上

s

到

t

路

径

上

的

最

小

边

\color{Red}对于树中任意两点s和t,s和t在原图的最小割等于最小割树上s到t路径上的最小边

对于树中任意两点s和t,s和t在原图的最小割等于最小割树上s到t路径上的最小边

构造完成之后,就可以树上倍增求两点间最小边权(就是lca的树上倍增)

考虑如何来构造

Ⅰ

.

选

择

图

中

任

意

两

点

,

求

出

最

小

割

,

在

最

小

割

树

中

连

接

这

两

点

,

边

权

为

最

小

割

Ⅰ.选择图中任意两点,求出最小割,在最小割树中连接这两点,边权为最小割

Ⅰ.选择图中任意两点,求出最小割,在最小割树中连接这两点,边权为最小割

Ⅱ

.

这

两

点

的

最

小

割

把

图

划

分

为

两

个

集

合

,

在

两

个

集

合

中

继

续

分

治

,

重

复

步

骤

Ⅰ

Ⅱ.这两点的最小割把图划分为两个集合,在两个集合中继续分治,重复步骤Ⅰ

Ⅱ.这两点的最小割把图划分为两个集合,在两个集合中继续分治,重复步骤Ⅰ

这样分集合最后会分到集合中只有1个点,算法结束,最小割树构造完成

至

于

最

小

割

树

为

什

么

有

这

样

的

定

理

,

我

只

有

自

己

的

感

性

理

解

\color{Red}至于最小割树为什么有这样的定理,我只有自己的感性理解

至于最小割树为什么有这样的定理,我只有自己的感性理解

所

有

读

者

感

兴

趣

自

行

去

了

解

吧

,

我

比

较

菜

,

记

住

就

好

了

。

所有读者感兴趣自行去了解吧,我比较菜,记住就好了。

所有读者感兴趣自行去了解吧,我比较菜,记住就好了。

#include <bits/stdc++.h>
using namespace std;
const int inf=1e9;
const int maxn=1e5+10;
struct edge{
  int to,nxt,flow;
}d[maxn]; int head[maxn],cnt=1;
void add(int u,int v,int flow){
  d[++cnt]=(edge){ v,head[u],flow },head[u]=cnt;
  d[++cnt]=(edge){ u,head[v],0 },head[v]=cnt;
}
int dis[maxn],n,m;
bool bfs(int s,int t)//普通的最大流找增广路 
{
  for(int i=0;i<=n+1;i++) dis[i]=0;
  dis[s]=1;
  queue<int>q; q.push( s );
  while( !q.empty() )
  {
    int u=q.front(); q.pop();
    for(int i=head[u];i;i=d[i].nxt )
    {
      int v=d[i].to;
      if( dis[v]==0&&d[i].flow )
      {
        dis[v]=dis[u]+1;
        if( v==t )  return true;
        q.push( v );
      }
    }
  }
  return false;
}
int dinic(int u,int t,int flow )//普通的最大流 
{
  if( u==t )  return flow;
  int res=flow;
  for(int i=head[u];i;i=d[i].nxt )
  {
    int v=d[i].to;
    if( dis[v]==dis[u]+1&&d[i].flow )
    {
      int temp=dinic(v,t,min(res,d[i].flow) );
      res-=temp;
      if( temp==0 ) dis[v]=0;
      d[i].flow-=temp;
      d[i^1].flow+=temp;
    }
    if( res==0 )  break;
  }
  return flow-res;
}
void init()
{
  for(int i=2;i<=cnt;i+=2)//撤流操作,因为上一次跑最大流改变了图的流量,改回来 
    d[i].flow=( d[i].flow+d[i^1].flow ),d[i^1].flow=0;
}
int maxflow(int s,int t)
{
  init();//退流
  int ans=0;
  while( bfs(s,t) ) ans+=dinic(s,t,inf);
  return ans; 
}
class GHT
{
  public:
    edge d[maxn];
    int head[maxn],cnt;
    int temp1[maxn],temp2[maxn],node[maxn];
    void add(int u,int v,int flow){
      d[++cnt]=(edge){ v,head[u],flow },head[u]=cnt;
      d[++cnt]=(edge){ u,head[v],flow},head[v]=cnt;
    }
    void build(int l,int r)
    {
      if( l>=r )  return;
      int x=node[l],y=node[l+1];
      int cut = maxflow(x,y);
      add(x,y,cut );
      int top1=0,top2=0;
      //去掉x和y,分成集合temp1和temp2 
      for(int i=l;i<=r;i++)
      {
        //最后一次bfs后有深度,说明和x相连接,放在左集合temp1 
        if( dis[ node[i] ] )  temp1[++top1]=node[i];
        else  temp2[++top2]=node[i]; 
      }
      for(int i=l;i<=l+top1-1;i++)  node[i]=temp1[i-l+1];
      for(int i=l+top1;i<=r;i++)  node[i]=temp2[i-top1-l+1];
      build(l,l+top1-1); build(l+top1,r);//两个集合分别建图 
    }
    int deep[maxn],fa[maxn][23],ans[maxn][23],log2n;
    void dfs(int x,int father)
    {
      fa[x][0]=father;
      deep[x]=deep[father]+1;
      for(int i=1;i<=log2n;i++)
      {
        fa[x][i]=fa[ fa[x][i-1] ][i-1];
        ans[x][i]=min( ans[x][i-1],ans[ fa[x][i-1] ][i-1]);
      }
      for(int i=head[x];i;i=d[i].nxt )
      {
        int v=d[i].to;
        if( v!=father )
        {
          ans[v][0]=d[i].flow;
          dfs(v,x);
        } 
      }
    }
    int query(int x,int y)
    {
      int zhi=inf;
      if( deep[x]<deep[y] ) swap(x,y);
      for(int i=log2n;i>=0;i-- )
        if( deep[ fa[x][i] ]>=deep[y] )
        {
          zhi=min(zhi,ans[x][i] );
          x=fa[x][i];
        }
      if( x==y )  return zhi;
      for(int i=log2n;i>=0;i-- )
      {
        if( fa[x][i]!=fa[y][i] )
        {
          zhi=min( zhi,min( ans[x][i],ans[y][i] ) );
          x=fa[x][i],y=fa[y][i];
        }
      }
      zhi=min(zhi,min( ans[x][0],ans[y][0] ) );
      return zhi;
    }
}CUT;
void CUT_init()
{
  CUT.log2n=log2(n)+1;
  CUT.cnt=1;//是链式前向星的边编号 
  for(int i=1;i<=n;i++) CUT.node[i]=i;//这是储存节点集合的信息 
  CUT.build(1,n);//建树 
  CUT.dfs(1,0);//倍增 
}
int main()
{
  scanf("%d%d",&n,&m);
  for(int i=1;i<=m;i++)
  {
    int l,r,flow; scanf("%d%d%d",&l,&r,&flow);
    add( l,r,flow );  add(r,l,flow);//无向图网络流建边 
  }
  CUT_init();//初始化最小割树 
  int q; scanf("%d",&q);
  for(int i=1;i<=q;i++)
  {
    int s,t; scanf("%d%d",&s,&t);
    int _= CUT.query(s,t);
    if( _==inf )  _=-1;
    printf("%d\n",_);
  }
}