正题

题目链接:https://ac.nowcoder.com/acm/contest/1221/H

---

题目大意

给一张图，要求删掉一些边使得最小生成树权值不变，然后求删掉的边的最小权值。

---

解题思路

我们假设能够构成最小生成树的边权之和为$sum$，最小生成树的边权之和为$k$，都是确定的，所以我们剩下任意一颗最小生成树答案都是不变的，所以我们计算出$sum$和$k$就行了。

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const int N=2e5+50; struct node{int x,y;ll w; }a[N]; int n,m,fa[N]; ll ans; bool cmp(node x,node y) {return x.w<y.w;} int find(int x) {if(fa[x]!=x) return fa[x]=find(fa[x]);return x; } int main() {scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)fa[i]=i;for(int i=1;i<=m;i++)scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].w);sort(a+1,a+1+m,cmp);for(int l=1,r=1;l<=m;l=r=r+1){while(a[r+1].w==a[l].w) r++;for(int j=l;j<=r;j++){int x=find(a[j].x),y=find(a[j].y);if(x!=y) ans+=a[j].w;}for(int j=l;j<=r;j++){int x=find(a[j].x),y=find(a[j].y);if(x!=y) ans-=a[j].w,fa[y]=x;}}printf("%lld",ans); }

总结

以上是生活随笔为你收集整理的牛客-Forsaken喜欢独一无二的树【并查集,最小生成树】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。