【洛谷P4897】【模板】最小割树（Gomory-Hu Tree） | Mrsrz's blog

最小割树

题目大意：

给定一张无向图，每条边带边权。

每次询问给定两个点，求它们的最小割。

题解：

最小割树。

对于一棵最小割树上的一条边 $(u,v)$，其边权表示原图中 $u,v$ 的最小割，并且这个最小割分成的两个集合中的点，恰被该树边分成两棵不同的子树。

而对于图上两点之间的最小割，其值等于最小割树上两点的简单路径上的最小的边权。

我们根据这个定义构造最小割树：

每次从当前点集中任选两个点 $S,T$，作为源点和汇点，并跑最小割（在完整的原图中）。

求出最小割的值，在树上连接 $S,T$，边权为最小割大小。

然后，我们 dfs 一遍，得到当前点集被最小割分成的两个点集。

分别对两个点集继续进行上述步骤，直到点集中只有 $1$ 个元素为止。

然后就可以方便地处理询问了。

本题 $n$ 较小，所以查询时可以直接在树上暴力。

Code：

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int N=505;
int n,head[N],cnt,m;
bool inq[N];
struct edge{
    int to,nxt,cap;
}e[N*10];
namespace tr{
    edge e[N<<1];
    int head[N],cnt,dep[N],fa[N],dis[N];
    inline void addedge(int u,int v,int w){
        e[++cnt]=(edge){v,head[u],w},head[u]=cnt;
        e[++cnt]=(edge){u,head[v],w},head[v]=cnt;
    }
    void dfs(int now){
        for(int i=head[now];i;i=e[i].nxt)
        if(!dep[e[i].to]){
            dep[e[i].to]=dep[now]+1;
            dis[e[i].to]=e[i].cap;
            fa[e[i].to]=now;
            dfs(e[i].to);
        }
    }
    void init(){
        dep[0]=1;
        dfs(0);
    }
    inline int ask(int x,int y){
        if(dep[x]<dep[y])swap(x,y);
        int ret=0x3f3f3f3f;
        while(dep[x]>dep[y])ret=min(ret,dis[x]),x=fa[x];
        while(x!=y)ret=min(ret,min(dis[x],dis[y])),x=fa[x],y=fa[y];
        return ret;
    }
}
namespace MF{
    int S,T;
    edge e[N*10];
    int head[N],cnt,dep[N],iter[N];
    bool vis[N];
    queue<int>q;
    void bfs(){
        dep[S]=1;
        for(q.push(S);!q.empty();){
            int u=q.front();q.pop();
            for(int i=head[u];i;i=e[i].nxt)
            if(e[i].cap&&!dep[e[i].to]){
                dep[e[i].to]=dep[u]+1;
                q.push(e[i].to);
            }
        }
    }
    int dfs(int u,int f){
        if(u==T||!f)return f;
        for(int&i=iter[u];i;i=e[i].nxt)
        if(e[i].cap&&dep[e[i].to]>dep[u]){
            int d=dfs(e[i].to,min(f,e[i].cap));
            if(d){
                e[i].cap-=d,e[i^1].cap+=d;
                return d;
            }
        }
        return 0;
    }
    int dinic(){
        for(int flow=0;;){
            for(int i=0;i<=n;++i)dep[i]=0,iter[i]=head[i];
            bfs();
            if(dep[T]==0)return flow;
            for(int f;f=dfs(S,0x3f3f3f3f);flow+=f);
        }
    }
    void DFS(int u){
        vis[u]=1;
        for(int i=head[u];i;i=e[i].nxt)
        if(e[i].cap&&!vis[e[i].to])DFS(e[i].to);
    }
    int maxflow(vector<int>&vq,int u,int v,vector<int>&L,vector<int>&R){
        S=u,T=v;
        cnt=1;
        for(int i=0;i<=n;++i)head[i]=0;
        for(int now=0;now<=n;++now){
            for(int i=::head[now];i;i=::e[i].nxt)
            if(now< ::e[i].to){
                e[++cnt]=(edge){::e[i].to,head[now],::e[i].cap},head[now]=cnt,
                e[++cnt]=(edge){now,head[::e[i].to],::e[i].cap},head[::e[i].to]=cnt;
            }
        }
        int ret=dinic();
        for(int i=0;i<=n;++i)vis[i]=0;
        DFS(S);
        for(int i=0;i<vq.size();++i)
        if(vis[vq[i]])L.push_back(vq[i]);else R.push_back(vq[i]);
        return ret;
    }
}
vector<int>vq;
void solve(vector<int>&vq){
    if(vq.size()==1)return;
    for(int i=0;i<vq.size();++i)inq[vq[i]]=1;
    int u=vq.front(),v=vq.back();
    vector<int>L,R;
    tr::addedge(u,v,MF::maxflow(vq,u,v,L,R));
    for(int i=0;i<vq.size();++i)inq[vq[i]]=0;
    solve(L);
    solve(R);
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;++i){
        int u,v,w;
        cin>>u>>v>>w;
        e[++cnt]=(edge){v,head[u],w},head[u]=cnt;
        e[++cnt]=(edge){u,head[v],w},head[v]=cnt;
    }
    for(int i=0;i<=n;++i)vq.push_back(i);
    solve(vq);
    tr::init();
    int t;
    for(cin>>t;t--;){
        int x,y;
        cin>>x>>y;
        cout<<tr::ask(x,y)<<'\n';
    }
    return 0;
}