嗯...

題目鏈接：https://www.luogu.org/problemnew/show/P1111

?

這道題的關(guān)鍵是讀懂題：

首先根據(jù)題中的一些扎眼的字眼我們可以判斷這是一道用最小生成樹來做的題...

?

但是注意一個東西：施工時是同時性的！！！！

所以，施工時間應(yīng)該是要施工的道路中所需時間的最大值...

換句話說，就是要求我們合并時最大的邊權(quán)，我們只需用一個ans來維護(hù)就行

?

其次，如何判斷是否存在“全部公路修復(fù)完畢仍然存在兩個村莊無法通車”的情況，這就要用到了生成樹的概念：

在一幅圖中將所有n個點連接起來的n-1條邊所形成的樹

而num我們存儲的即為邊的數(shù)量，將它與n-1進(jìn)行比較即可

?

思路：

在最小生成樹的模板的基礎(chǔ)上進(jìn)行修改，在合并x點和y點的時候用num記錄所修的道路數(shù)量，用ans記錄邊權(quán)的最大值，上面已經(jīng)說過，邊權(quán)最大值即為所需的時間...最后輸出時將num與n-1進(jìn)行比較

?

AC代碼：

1 #include<cstdio> 2 #include<iostream> 3 #include<algorithm> 4 5 using namespace std; 6 7 int f[10005], ans; 8 int num; 9 10 struct node{ 11 int x, y, l; 12 } a[100005]; 13 14 inline int cmp(node i, node j){ 15 return i.l < j.l; 16 } 17 18 inline int find(int x){ 19 if(f[x] != x) 20 f[x] = find(f[x]); 21 return f[x]; 22 } 23 24 int main(){ 25 int n, m; 26 scanf("%d%d", &n, &m); 27 for(int i = 1; i <= n; i++) 28 f[i] = i; 29 for(int i = 1; i <= m; i++){ 30 scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].l); 31 } 32 sort(a+1, a+m+1, cmp); 33 for(int i = 1; i <= m; i++){ 34 int r1 = find(a[i].x); 35 int r2 = find(a[i].y); 36 if(r1 != r2){ 37 f[r1] = r2; 38 num++;//道路數(shù)量 39 ans = max(ans, a[i].l);//時間 40 } 41 } 42 if(num >= n - 1) printf("%d", ans); 43 else printf("-1"); 44 return 0; 45 } AC代碼

?

轉(zhuǎn)載于:https://www.cnblogs.com/New-ljx/p/10779712.html

總結(jié)

以上是生活随笔為你收集整理的洛谷 P1111 修复公路（最小生成树）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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