正題

題目鏈接:https://ac.nowcoder.com/acm/contest/1221/H

---

題目大意

給一張圖，要求刪掉一些邊使得最小生成樹(shù)權(quán)值不變，然后求刪掉的邊的最小權(quán)值。

---

解題思路

我們假設(shè)能夠構(gòu)成最小生成樹(shù)的邊權(quán)之和為$sum$，最小生成樹(shù)的邊權(quán)之和為$k$，都是確定的，所以我們剩下任意一顆最小生成樹(shù)答案都是不變的，所以我們計(jì)算出$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); }

總結(jié)

以上是生活随笔為你收集整理的牛客-Forsaken喜欢独一无二的树【并查集,最小生成树】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。