首先观察题意,这是一个无向图,因此需要双向建边,两条边的反向边恰好是对方,且都有相同的容量,这和反悔概念是不同的!

就比如说$x$携带了$w$单位流量到了$y$,如果是有向图,未来也只能把$w$单位流量"退"回去。

如果是无向图,不仅可以把$w$单位流量“退”回去,还可以多携带$w$单位流量到$x$,总共是$2*w$的流量。

因为这个WA了,想了好一会。

进入正题,

对于单点对最小割,直接ISAP就好了。

对于多点对最小割,就需要用到最小割树Gomory-Hu Tree

考虑贡献吧,对于含有两条边及以上的路径,它的贡献来自于路径上的最小的边权,而在计算只有一条边的路径时,已经覆盖了所有的边。

因此只需把不同边权的边的数目统计出来就好了

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define gc getchar()
#define ll long long
using namespace std;
const int N=855,M=8555;
template<class o>
inline void qr(o &x)
{
    x=0;char c=gc;int f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
template<class o>
void qw(o x)
{
    if(x<0)putchar('-'),x=-x;
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
struct node{int x,y,c;}e[M];
struct edge{int y,c,next;}a[M<<1];int last[N],len,n,m,cur[N];
void ins(int x,int y,int c)
{
    a[++len]=(edge){y,c,last[x]};last[x]=len;
    a[++len]=(edge){x,c,last[y]};last[y]=len;
}
namespace GHTree
{
    int q[N],l,r,s,t,d[N],gap[N];
    void init()
    {
        len=1;memset(last,0,sizeof(last));
        for(int i=1;i<=m;i++)ins(e[i].x,e[i].y,e[i].c);
        memset(gap,0,sizeof(gap));
        q[l=r=1]=t;memset(d,0,sizeof(d));++gap[d[t]=1];
        for(int x=q[l],y;l<=r;x=q[++l])for(int k=last[x];k;k=a[k].next)if(!d[y=a[k].y])++gap[d[y]=d[x]+1],q[++r]=y;
    }
    int flow(int x,int f)
    {
        if(x==t)return f;
        int sum=0,tmp;
        for(int &k=cur[x],y;k;k=a[k].next)
            if(d[y=a[k].y]+1==d[x])
            {
                sum+=(tmp=flow(y,min(a[k].c,f)));
                f-=tmp;a[k].c-=tmp;a[k^1].c+=tmp;
                if(!f)return sum;
            }
        if(!(--gap[d[x]]))d[s]=n+1;
        ++gap[++d[x]];cur[x]=last[x];
        return sum;
    }
    int ISAP(int x,int y)
    {
        s=x,t=y;
        init();int ans=0;
        memcpy(cur,last,sizeof cur);
        while(d[s]<=n)ans+=flow(s,1e9);
        return ans;
    }
    int sta[N],p[N],tot,col[N],ans[N],cnt;
    void clr(int x)
    {
        col[x]=tot;
        for(int k=last[x],y;k;k=a[k].next)
            if(col[y=a[k].y]!=tot&&a[k].c)clr(y);
    }
    void build(int l,int r)
    {
        if(l==r)return ;
        int x=p[l],y=p[l+1];
        int cut=ISAP(x,y);++tot;
        clr(x);int L=l,R=r;
        for(int i=l;i<=r;i++)
            if(col[p[i]]==tot)sta[L++]=p[i];
            else sta[R--]=p[i];
        for(int i=l;i<=r;i++)p[i]=sta[i];
        ans[++cnt]=cut;
        build(l,L-1);build(R+1,r);
    }
    void solve()
    {
        cnt=0;tot=0;
        for(int i=1;i<=n;i++)p[i]=i;
        build(1,n);
        sort(ans+1,ans+cnt+1);
        int tp=0;
        for(int i=1;i<=cnt;i++)if(i==1||ans[i-1]!=ans[i])ans[++tp]=ans[i];
        qw(tp);puts("");
    }
}
int main()
{
    //freopen("cuts1.in","r",stdin);
    qr(n),qr(m);
    for(int i=1,x,y,c;i<=m;i++)qr(x),qr(y),qr(c),e[i]=(node){x,y,c};
    GHTree::solve();
    return 0;
}