Problem Description 隨著杭州西湖的知名度的進一步提升，園林規劃專家湫湫希望設計出一條新的經典觀光線路，根據老板馬小騰的指示，新的風景線最好能建成環形，如果沒有條件建成環形，那就建的越長越好。 現在已經勘探確定了n個位置可以用來建設，在它們之間也勘探確定了m條可以設計的路線以及他們的長度。請問是否能夠建成環形的風景線？如果不能，風景線最長能夠達到多少？ 其中，可以興建的路線均是雙向的，他們之間的長度均大於0。 Input 測試數據有多組，每組測試數據的第一行有兩個數字n, m，其含義參見題目描述； 接下去m行，每行3個數字u v w，分別代表這條線路的起點，終點和長度。 [Technical Specification] 1. n<=100000 2. m <= 1000000 3. 1<= u, v <= n 4. w <= 1000 Output 對於每組測試數據，如果能夠建成環形（並不需要連接上去全部的風景點），那麼輸出YES，否則輸出最長的長度，每組數據輸出一行。 Sample Input 3 3 1 2 1 2 3 1 3 1 1 Sample Output YES Source 2013騰訊編程馬拉松初賽第二場（3月22日） Recommend liuyiding 解題思路：比賽的時候還傻不拉幾的當做最長路做，其實就是並查集的簡單題而已。一是並查集判環，有環就輸出YES，否則將根節點加上到根節點的邊的邊權就是以此根節點為根的生成樹的各邊權值之和，若圖中有兩個或以上獨立的連通分量，則取這些樹中各邊權值和最高的作為答案即可。 [cpp] #include<iostream> #include<cstdio> #include<cstring> using namespace std; int father[100005],num[100005],sum[100005]; long ans,cnt; void ini() { int i; for(i=0;i<100005;i++) { num[i]=1; father[i]=i; } memset(sum,0,sizeof(sum)); } int find(int x) { if(x==father[x]) return x; return father[x]=find(father[x]); } bool Union(int s,int e,int w) { int a=find(s); int b=find(e); if(a!=b) { if(num[a]>num[b]) { father[b]=a; num[a]+=num[b]; sum[a]+=sum[b]+w; } else { father[a]=b; num[b]+=num[a]; sum[b]+=sum[a]+w; } return true; } return false; } int main() { int m,n,i,a,b,c; bool flag; while(scanf("%d%d",&m,&n)!=-1) { ini(); ans=0; flag=false; for(i=0;i<n;i++) { scanf("%d%d%d",&a,&b,&c); if(flag) continue; if(!Union(a,b,c)) { flag=true; continue; } } if(flag) printf("YES\n"); else { for(i=1;i<=m;i++) if(ans<sum[i]) ans=sum[i]; printf("%d\n",ans); } } return 0; }
