[文章目录]
Description
我们可以把视野放宽，考虑有N个点的无向连通图中所有点对的最小割的容量，共能得到N(N−1)/2个数值。这些数值中互不相同的有多少个呢？这似乎是个有趣的问题。1<=N<=850 1<=M<=8500 1<=W<=100000
最小割树上不同边权个数即为所求
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int inf=0x3f3f3f3f;
#define N 1000
#define M 20000
int n,m,s,t;
int head[N],to[M],nxt[M],f[M],cnt=1;
inline void add(int x,int y,int z)
{
to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt; f[cnt]=z;
to[++cnt]=x; nxt[cnt]=head[y]; head[y]=cnt; f[cnt]=z;
}
queue<int>q;
int dis[N];
bool bfs()
{
memset(dis,-1,sizeof dis);
while(!q.empty()) q.pop();
q.push(s); dis[s]=0; int x,i;
while(!q.empty())
{
x=q.front(); q.pop();
for(i=head[x];i;i=nxt[i]) if(f[i]>0&&dis[to[i]]==-1)
{
dis[to[i]]=dis[x]+1;
if(to[i]==t) return true;
q.push(to[i]);
}
}
return false;
}
int dinic(int x,int flow)
{
if(x==t) return flow;
int xx,tmp=flow;
for(int i=head[x];i;i=nxt[i]) if(f[i]>0&&dis[to[i]]==dis[x]+1)
{
xx=dinic(to[i],min(tmp,f[i]));
if(!xx) dis[to[i]]=-1;
f[i]-=xx; f[i^1]+=xx; tmp-=xx;
if(!tmp) return flow;
}
return flow-tmp;
}
int p[N],cg[N],g[N],tot;
bool vis[N];
void dfs(int x)
{
vis[x]=1;
for(int i=head[x];i;i=nxt[i]) if(f[i]>0&&!vis[to[i]]) dfs(to[i]);
}
void solve(int l,int r)
{
if(l==r) return ;
s=p[l]; t=p[r]; ++tot;
int i,i1=l,i2=r;
for(i=2;i<=cnt;i+=2) f[i]=f[i^1]=(f[i]+f[i^1])>>1;
while(bfs()) g[tot]+=dinic(s,inf);
memset(vis,0,sizeof vis);
dfs(s);
for(i=l;i<=r;++i)
{
if(vis[p[i]]) cg[i1++]=p[i];
else cg[i2--]=p[i];
}
for(i=l;i<=r;++i) p[i]=cg[i];
solve(l,i2); solve(i1,r);
}
int main()
{
scanf("%d%d",&n,&m);
int i,x,y,z;
for(i=1;i<=m;++i)
{
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
}
for(i=1;i<=n;++i) p[i]=i;
solve(1,n);
sort(g+1,g+tot+1);
for(x=1,i=2;i<=tot;++i) x+=(g[i]!=g[i-1]);
printf("%d",x);
return 0;
}