题目描述
学过图论的同学都知道最小割的概念：对于一个图，某个对图中结点的划分将图中所有结点分成两个部分，如果结点 s,ts,t 不在同一个部分中，则称这个划分是关于 s,ts,t 的割。对于带权图来说，将所有顶点处在不同部分的边的权值相加所得到的值定义为这个割的容量，而 s,ts,t 的最小割指的是在关于 s,ts,t 的割中容量最小的割。

而对冲刺 NOI 竞赛的选手而言，求带权图中两点的最小割已经不是什么难事了。我们可以把视野放宽，考虑有 NN 个点的无向连通图中所有点对的最小割的容量，共能得到 N(N-1)/2N(N−1)/2 个数值。这些数值中互不相同的有多少个呢？这似乎是个有趣的问题。

输入格式
第一行包含两个数 N,MN,M，表示点数和边数。

接下来 MM 行，每行三个数 u,v,wu,v,w，表示点 uu 和点 vv (从 11 开始标号) 之间有一条权值是 ww 的边。

输出格式
第一行为一个整数，表示不同的最小割容量的个数。

输入输出样例
输入 #1复制
4 4
1 2 3
1 3 6
2 4 5
3 4 4
输出 #1复制
3
说明/提示
1\leq N\leq 850,1\leq M\leq 8500,1\leq w\leq 1000001≤N≤850,1≤M≤8500,1≤w≤100000。

最小割树的裸题。

先求出最小割树，然后枚举两个点，将答案放进set即可。

AC代码：

#include<bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
const int N=1010,M=1e5+10;
int n,m,q;
struct maxflow{
    int head[N],nex[M],to[M],w[M],h[N],tot=1,s,t;   queue<int> q;  
    inline void ade(int a,int b,int c){
        to[++tot]=b; nex[tot]=head[a]; w[tot]=c; head[a]=tot;
    }
    inline void add(int a,int b,int c){ade(a,b,c);  ade(b,a,0);}
    inline int bfs(){
        q.push(s);  memset(h,0,sizeof h);   h[s]=1;
        while(q.size()){
            int u=q.front();    q.pop();
            for(int i=head[u];i;i=nex[i]){
                if(w[i]&&!h[to[i]]){
                    h[to[i]]=h[u]+1;    q.push(to[i]);
                }
            }
        }
        return h[t];
    }
    int dfs(int x,int f){
        if(x==t)    return f;   int fl=0;
        for(int i=head[x];i&&f;i=nex[i]){
            if(w[i]&&h[to[i]]==h[x]+1){
                int mi=dfs(to[i],min(w[i],f));
                w[i]-=mi,w[i^1]+=mi,fl+=mi,f-=mi;
            }
        }
        if(!fl) h[x]=-1;
        return fl;
    }
    inline void init(){
    	for(int i=2;i<=tot;i+=2)	w[i]+=w[i^1],w[i^1]=0;
	}
    inline int dinic(){
        int res=0;  init();
        while(bfs())    res+=dfs(s,inf);
        return res;
    }
}d;
struct min_cut_tree{
    int head[N],nex[M],to[M],w[M],tot=0;
    inline void ade(int a,int b,int c){
        to[++tot]=b; nex[tot]=head[a]; w[tot]=c; head[a]=tot;
    }
    inline void add(int a,int b,int c){ade(a,b,c);  ade(b,a,0);}
    int a[N],b[N],c[N];
    void build(int l,int r){
        if(l==r)    return ;
        d.s=a[l],d.t=a[l+1];    int flow=d.dinic();
        add(a[l],a[l+1],flow);
        int cnt1=0,cnt2=0;
        for(int i=l;i<=r;i++){
            if(d.h[a[i]])   b[++cnt1]=a[i];
            else    c[++cnt2]=a[i];
        }
        for(int i=l;i<=l+cnt1-1;i++)    a[i]=b[i-l+1];
        for(int i=l+cnt1;i<=r;i++)  a[i]=c[i-cnt1-l+1];
        build(l,l+cnt1-1);  build(l+cnt1,r);
    }
    int h[N],f[N][10],mi[N][10],lg[N];
    void dfs(int x,int fa){
        h[x]=h[fa]+1;
        for(int i=1;(1<<i)<=h[x];i++){
            f[x][i]=f[f[x][i-1]][i-1];
            mi[x][i]=min(mi[x][i-1],mi[f[x][i-1]][i-1]);
        }
        for(int i=head[x];i;i=nex[i]){
            if(to[i]==fa)   continue;
            f[to[i]][0]=x; mi[to[i]][0]=w[i];
            dfs(to[i],x);
        }
    }
    void solve(){
        for(int i=1;i<=n;i++)   lg[i]=lg[i-1]+(1<<lg[i-1]==i);
        for(int i=1;i<=n;i++)   a[i]=i;
        build(1,n); dfs(1,0);
    }
    inline int ask(int x,int y){
        int res=inf;
        if(h[x]<h[y])   swap(x,y);
        while(h[x]>h[y]){
            res=min(res,mi[x][lg[h[x]-h[y]]-1]);
            x=f[x][lg[h[x]-h[y]]-1];
        }
        if(x==y)    return res;
        for(int i=lg[h[x]]-1;i>=0;i--){
            if(f[x][i]!=f[y][i]){
                res=min(res,mi[x][i]); res=min(res,mi[y][i]);
                x=f[x][i],y=f[y][i];
            }
        }
        res=min(res,mi[x][0]); res=min(res,mi[y][0]);
        return res;
    }
}mct;
set<int> st;
int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    cin>>n>>m;
    for(int i=1,a,b,c;i<=m;i++) cin>>a>>b>>c,d.add(a,b,c),d.add(b,a,c);
    mct.solve();
    for(int i=1;i<=n;i++)	for(int j=i+1;j<=n;j++)	st.insert(mct.ask(i,j));
    cout<<st.size()<<'\n';
    return 0;
}