$ \rightarrow $ 戳我進CH原題

走廊潑水節 0x60「圖論」例題

總時限10 s $ \quad $ 總內存256 MiB
　

描述

【簡化版題意】給定一棵N個節點的樹，要求增加若干條邊，把這棵樹擴充為完全圖，并滿足圖的唯一最小生成樹仍然是這棵樹。
求增加的邊的權值總和最小是多少。
　
我們一共有 $ N $ 個OIER打算參加這個潑水節，同時很湊巧的是正好有 $ N $ 個水龍頭(至于為什么，我不解釋)。
$ N $ 個水龍頭之間正好有 $ N-1 $ 條小道，并且每個水龍頭都可以經過小道到達其他水龍頭(這是一棵樹，你應該懂的..)。
但是OIER門為了迎接中中的挑戰，決定修建一些個道路(至于怎么修，秘密~),
使得每個水龍頭到每個水龍頭之間都有一條直接的道路連接(也就是構成一個完全圖唄~)。
但是OIER門很懶得，并且記性也不好，他們只會去走那 $ N-1 $ 條小道，
并且希望所有水龍頭之間修建的道路，都要大于兩個水龍頭之前連接的所有小道(小道當然要是最短的了)。
所以神COW們，幫那些OIER們計算一下吧，修建的那些道路總長度最短是多少，畢竟修建道路是要破費的~~
　

輸入格式

本題為多組數據~
第一行 $ t $ ，表示有t組測試數據
對于每組數據
第一行 $ N $ ，表示水龍頭的個數（當然也是OIER的個數）；
$ 2 $ 到 $ N $ 行，每行三個整數 $ X,Y,Z $ ；表示水龍頭 $ X $ 和水龍頭 $ Y $ 有一條長度為 $ Z $ 的小道
　

輸出格式

對于每組數據，輸出一個整數，表示修建的所有道路總長度的最短值。
　

樣例輸入

231 2 21 3 341 2 32 3 43 4 5

樣例輸出

417

　

數據范圍與約定

每個測試點最多 $ 10 $ 組測試數據
$ 50 $ % $ n \le 1500 $ ;
$ 100 $ % $ n \le 6000 $ ;
$ 100 $ % $ z \le 100 $ ;
　

樣例解釋

第一組數據，在 $ 2 $ 和 $ 3 $ 之間修建一條長度為 $ 4 $ 的道路，
使這棵樹變成一個完全圖，且原來的樹依然是這個圖的唯一最小生成樹.
　

題解

• 對給定樹上的 $ N-1 $ 條邊模擬一遍 $ Kruskal $

• 通過邊 $ (x,y) $ 合并兩個并查集

• $ x $ 集合中的每個點到 $ y $ 集合中的每個點

• 添加一條長度為 $ w(x,y)+1 $ 的邊

代碼

#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> using namespace std; #define maxn 6010 struct edge{ int u,v,w; }e[maxn]; int t,n,f[6010],s[6010]; long long ans; bool cmp(edge x,edge y){ return x.w<y.w; } int find(int x){if(f[x]!=x) f[x]=find(f[x]);return f[x]; } int main(){scanf("%d",&t);while(t--){scanf("%d",&n);for(int i=1;i<=n;++i){ f[i]=i; s[i]=1; }for(int i=1;i<n;++i) scanf("%d %d %d",&e[i].u,&e[i].v,&e[i].w);sort(e+1,e+n,cmp); ans=0;for(int fu,fv,i=1;i<n;++i){fu=find(e[i].u); fv=find(e[i].v);if(fu==fv) continue;ans+=1ll*(e[i].w+1)*(s[fu]*s[fv]-1);f[fu]=fv;s[fv]+=s[fu];}printf("%lld\n",ans);}return 0; } /* 用時 32 ms 占用內存 384 KiB */

轉載于:https://www.cnblogs.com/PotremZ/p/CH6201.html

總結

以上是生活随笔為你收集整理的Contest Hunter CH6201 走廊泼水节 最小生成树 Kruskal的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。