湫湫系列故事——设计风景线
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 676 Accepted Submission(s): 219
Problem Description
随着杭州西湖的知名度的进一步提升,园林规划专家湫湫希望设计出一条新的经典观光线路,根据老板马小腾的指示,新的风景线最好能建成环形,如果没有条件建成环形,那就建的越长越好。
现在已经勘探确定了n个位置可以用来建设,在它们之间也勘探确定了m条可以设计的路线以及他们的长度。请问是否能够建成环形的风景线?如果不能,风景线最长能够达到多少?
其中,可以兴建的路线均是双向的,他们之间的长度均大于0。
现在已经勘探确定了n个位置可以用来建设,在它们之间也勘探确定了m条可以设计的路线以及他们的长度。请问是否能够建成环形的风景线?如果不能,风景线最长能够达到多少?
其中,可以兴建的路线均是双向的,他们之间的长度均大于0。
Input
测试数据有多组,每组测试数据的第一行有两个数字n, m,其含义参见题目描述;
接下去m行,每行3个数字u v w,分别代表这条线路的起点,终点和长度。
接下去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
Recommend
liuyiding
题解有误,题意已改,题解适用于加所有分支的最长路
思路:简单并查集,狂吐血,思维实在是太狭隘了。
#include<iostream> #include<cstring> #include<cstdio> using namespace std; const int mm=1e5+9; int root[mm],ran[mm]; int n,m,ans; void data() { ans=0; for(int i=0;i<=n;++i) root[i]=i,ran[i]=0; } int look(int x) { if(root[x]^x) root[x]=look(root[x]); return root[x]; } void uni(int x,int y) { x=look(x);y=look(y); root[y]=x;ran[x]+=ran[y]; if(ans<ran[x])ans=ran[x]; } int main() { int a,b,c,aa,bb; while(scanf("%d%d",&n,&m)!=EOF) { data(); bool flag=0; for(int i=0;i<m;++i) { scanf("%d%d%d",&a,&b,&c); aa=look(a);bb=look(b);ran[aa]+=c; if(aa^bb)uni(aa,bb); else flag=1; } if(flag)printf("YES\n"); else printf("%d\n",ans); } }