Forsaken喜欢独一无二的树

众所周知，最小生成树是指使图中所有节点连通且边权和最小时的边权子集。

不过最小生成树太简单了，我们现在来思考一个稍微复杂一点的问题。

现在给定一个 $n$ 个点， $m$ 条边的图，每条边 $e_i$ 都有一个权值 $w_i$ 。定义删除一条边 $e_i$ 的代价为 $w_i$ ，并且你可以对这个图执行任意次删边操作。

设这个图的最小生成树权值和为 $sum$ ，定义一个图的最小生成树是独一无二的当且仅当这个图的边集中没有除最小生成树外的其他子集能满足权值和为sum且使得所有点连通。一个图刚开始可能没有独一无二的最小生成树，现在你可以删除一些边，使得剩下的边的最小生成树大小依然为 $sum$ 并且这个图的最小生成树是独一无二的。

现在我们想要知道删除的边的权值和最小是多少？

#include<bits/stdc++.h> using namespace std; struct node { int x,y,w; }E[200005]; bool cmp(node a,node b) { return a.w<b.w; } int n,m,V[200005]; int find(int a) { if(a==V[a])return a; return V[a]=find(V[a]); } int main() { int i,j,k,a,b; long long ans=0; scanf("%d%d",&n,&m); for(i=1;i<=n;i++)V[i]=i; for(i=0;i<m;i++)scanf("%d%d%d",&E[i].x,&E[i].y,&E[i].w); sort(E,E+m,cmp); for(i=0;i<m;i=j) { for(j=i+1;j<m&&E[i].w==E[j].w;j++); for(k=i;k<j;k++) { a=find(E[k].x),b=find(E[k].y); if(a!=b)ans+=E[k].w; } for(k=i;k<j;k++) { a=find(E[k].x),b=find(E[k].y); if(a!=b)V[a]=b,ans-=E[k].w; } } printf("%lld\n",ans); return 0; }

详情