HDU 4514 湫湫系列故事——设计风景线


 
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;  
}

补充：软件开发 , C++ ,