（未完待续）

题目链接：Luogu P4123/BZOJ 4519/LibreOJ 2042/CQOI2016 D1T1。

一道 最小割树 的模板题，或者是一道 CDQ 分治 的好题。

题目

题意简述

一张 $n$ 个点 $m$ 条边的图，每一对点的最小割中，有多少个互不相同。

数据范围

$$1\leq n\leq 850$$

$$1\leq m\leq 8500$$

$$1\leq w\leq 10^5$$

时空限制

$$\text{Luogu}:3\text{s}/500\text{MiB}$$

$$\text{BZOJ}:20\text{s}/512\text{MiB}$$

$$\text{LibreOJ}:1\text{s}/256\text{MiB}$$

题解

思路

下面先介绍最小割树。

显然，对于某一个点来说，如果我们将它与另外一个点先求一遍最小割，那么整个图将会变成具有两个残留网络（如果原图不连通将会有更多）。

形如下面这个样子：

其中 $1$ 和 $2$ 的最小割为 $4$，有两种割法（用红、蓝标识）。而残余的边则分别属于两个联通块，把满流的边去掉，发现分成了 $(1,3,4)$、$(2,6)$ 和 $(5)$。

这里把 $2,6$ 看作和 $5$ 在一起。

为了生成最小割树，我们应该向最小割树中的 $1$ 和 $2$ 连一条边权为 $4$ 的边。

再举一个例子。

$1$ 和 $3$ 的最小割为 $9$，所以我们应该向最小割树中的 $1$ 和 $3$ 连一条边权为 $9$ 的边。

最后生成的最小割树长下面这个样子。

我们可以发现，每对点间路径的边权最小值即为它们之间的最小割。这就是最小割树的性质。

当然本题并不需要我们真的生成最小割树，然后在树上进行一番神奇的操作，只需要按层次来构造这棵树即可，保留边权，用 std::set 统计答案。

最后提醒一下，因为本题是无向边，所以反向边流量直接设成 $w_i$ 即可，防止加更多的边浪费空间。

代码

鉴于使用了网络流，本题不分析时间复杂度。但还是给出了大致的结果 $\Theta(2^{\left\lceil\log n\right\rceil}\alpha(n))$，其中 $\alpha(n)$ 为求一次网络流的时间复杂度。

#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
typedef unsigned long long ull;
#define INF 0X3F3F3F3F
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){ //读入优化
    reg bool f=false;
    reg char ch=getchar();
    reg int res=0;
    while(ch<'0'||'9'<ch)f|=(ch=='-'),ch=getchar();
    while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
    return f?-res:res;
}

const int MAXN=850+5; //点数数据范围
const int MAXM=8500+5; //边数数数据范围

inline void Read(void);
inline void Work(void);

int main(void){
    Read();
    Work();
    return 0;
}

int n,m;
int cnt=1,head[MAXN],to[MAXM<<1],w[MAXM<<1],W[MAXM<<1],Next[MAXM<<1]; //邻接表存边

inline void Add_Edge(reg int u,reg int v,reg int len){
    Next[++cnt]=head[u];
    to[cnt]=v;
    w[cnt]=len;
    W[cnt]=len; //用 W[] 存储原图的边权，防止 Dinic 后边权出现变化
    head[u]=cnt;
    return;
}

inline void Add_Tube(reg int u,reg int v,reg int len){
    Add_Edge(u,v,len); //正常的边
    Add_Edge(v,u,len); //本题是无向边，所以反向边流量直接设为 w，防止加更多的边浪费空间。
    return;
}

inline void Read(void){
    n=read(),m=read();
    for(reg int i=1;i<=m;++i){ //按照要求读入
        static int u,v,w;
        u=read(),v=read(),w=read();
        Add_Tube(u,v,w); //加边
    }
    return;
}

int dep[MAXN];
queue<int> Q;

inline bool BFS(int s,reg int t){ //BFS 判断是否联通
    memset(dep,-1,sizeof(dep));
    while(!Q.empty())Q.pop();
    dep[s]=1,Q.push(s);
    while(!Q.empty()){
        reg int ID=Q.front();
        Q.pop();
        for(reg int i=head[ID];i;i=Next[i])
            if(dep[to[i]]==-1&&w[i]>0){
                dep[to[i]]=dep[ID]+1;
                Q.push(to[i]);
            }
    }
    return dep[t]!=-1; //返回汇点是否可达
}

int cur[MAXN]; //用于当前弧优化

inline int DFS(reg int ID,reg int t,reg int lim){
    if(ID==t)
        return lim;
    reg int flow=0;
    for(reg int &i=cur[ID];i;i=Next[i])
        if(dep[to[i]]==dep[ID]+1&&w[i]>0){
            reg int f=DFS(to[i],t,min(lim-flow,w[i]));
            if(f){
                flow+=f;
                w[i]-=f;
                w[i^1]+=f;
                if(flow==lim)
                    break;
            }
        }
    return flow;
}

inline int Dinic(reg int s,reg int t){
    reg int res=0;
    while(BFS(s,t)){
        memcpy(cur,head,sizeof(head)); //复制邻接表表头
        res+=DFS(s,t,INF);
    }
    return res;
}

bool vis[MAXN];

inline void DFS(reg int ID){
    vis[ID]=true;
    for(reg int i=head[ID];i;i=Next[i])
        if(!vis[to[i]]&&w[i]>0)
            DFS(to[i]);
    return;
}

int fa[MAXN];
set<int> S;

inline void Work(void){
    for(reg int i=2;i<=n;++i)
        fa[i]=1; //初始化
    for(reg int i=2;i<=n;++i){
        reg int s=i,t=fa[i]; //求最小割的点对
        memcpy(w,W,sizeof(W)); //拷贝边权
        int ans=Dinic(s,t); //记录最小割
        S.insert(ans); //插入 set
        memset(vis,false,sizeof(vis)); //清空标记
        DFS(s); //开始寻找被隔开的点对
        for(reg int j=i;j<=n;++j)
            if(fa[j]==t&&vis[j])
                fa[j]=s;
    }
    printf("%d\n",(int)S.size()); //输出多少种，set 自动去重
    return;
}