最小割树

P4897 【模板】最小割树（Gomory-Hu Tree）

题意：求任意两个点的最小割。

首先任取两个点 \(s,t\) ，算出这两个点的最小割，然后将这两个点连上权值为 \(w\) 的边。求最小割的过程中，图被分为了两个联通块。在这两个联通块中递归执行上述过程，就能建成最小割树。

任意两个点的最小割，就是它们在树上的路径中边权的最小值。

下面的代码给出的是非递归建树的写法。

\(code:\)

#include<iostream>
#include<queue>
#include<cstdio>
using namespace std;
const int maxn=2e5+5;
int n,m,q,s,t,u,v,w,tot,flow,lg[maxn],vis[maxn],nxt[maxn],head[maxn],ver[maxn],edge[maxn],edge2[maxn],now[maxn],d[maxn],fa[maxn][20],dis[maxn][20],dep[maxn];
void add(int x,int y,int z){
    nxt[++tot]=head[x];head[x]=tot;
    ver[tot]=y;edge[tot]=edge2[tot]=z;
}
bool bfs(){
    queue <int> q;
    for(int i=1;i<=n;++i)
        d[i]=0;
    d[s]=1;now[s]=head[s];q.push(s);
    while(!q.empty()){
        int x=q.front();q.pop();
        for(int i=head[x];i;i=nxt[i])
            if(!d[ver[i]]&&edge[i]){
                d[ver[i]]=d[x]+1;
                now[ver[i]]=head[ver[i]];
                if(ver[i]==t)
                    return 1;
                q.push(ver[i]);
            }
    }
    return 0;
}
int dfs(int x,int sum){
    if(x==t)
        return sum;
    int re=sum,k;
    for(int i=now[x];i&&re;i=nxt[i]){
        now[x]=i;
        if(d[ver[i]]==d[x]+1&&edge[i]){
            k=dfs(ver[i],min(re,edge[i]));
            if(!k)
                d[ver[i]]=0;
            edge[i]-=k;edge[i^1]+=k;re-=k;
        }
    }
    return sum-re;
}
void dfs2(int x){
    vis[x]=1;
    for(int i=head[x];i;i=nxt[i])
        if(!vis[ver[i]]&&edge[i]>0)
            dfs2(ver[i]);
}
int dinic(int s,int t){
    int ans=0,sum=0;
    for(int i=1;i<=tot;++i)
        edge[i]=edge2[i];
    while(bfs())
        while(sum=dfs(s,1e9))
            ans+=sum;
    return ans;
}
int main(){
    scanf("%d%d",&n,&m);
    tot=1;
    for(int i=1;i<=m;++i){
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);add(v,u,w);
    }
    for(int i=1;i<=n;++i)
        fa[i][0]=1;
    dis[1][0]=1e9;
    for(int i=2;i<=n;++i){
        s=i;t=fa[s][0];
        flow=dinic(s,t);
        dis[s][0]=flow;
        for(int j=1;j<=n;++j)
            vis[j]=0;
        dfs2(s);
        for(int j=i+1;j<=n;++j)
            if(vis[j]&&fa[j][0]==t)
                fa[j][0]=s;
    }
    dep[1]=1;
    for(int i=2;i<=n;++i){
        dep[i]=dep[fa[i][0]]+1;
        lg[i]=lg[i-1]+((1<<(lg[i-1]+1))==i);
    }
    for(int j=1;j<=19;++j)
        for(int i=2;i<=n;++i){
            fa[i][j]=fa[fa[i][j-1]][j-1];
            dis[i][j]=min(dis[i][j-1],dis[fa[i][j-1]][j-1]);
        }
    scanf("%d",&q);
    for(int i=1;i<=q;++i){
        scanf("%d%d",&u,&v);
        if(dep[u]<dep[v])
            swap(u,v);
        int ans=1e9;
        while(dep[u]>dep[v]){
            ans=min(ans,dis[u][lg[dep[u]-dep[v]]]);
            u=fa[u][lg[dep[u]-dep[v]]];
        }
        if(u!=v){
            for(int i=19;i>=0;--i)
                if(fa[u][i]!=fa[v][i]){
                    ans=min(ans,min(dis[u][i],dis[v][i]));
                    u=fa[u][i],v=fa[v][i];
                }
            ans=min(ans,min(dis[u][0],dis[v][0]));
        }
        printf("%d\n",ans);
    }
    return 0;
}

P4123 [CQOI2016] 不同的最小割

仍然按照上面的方式建树，只需要统计树上边的种类即可。