hdu-----(4514)湫湫系列故事——设计风景线(树形DP+并查集)

By | 09月15日
Advertisement

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

Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 3105 Accepted Submission(s): 562

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日)

思路> 初看此题,以为是一个单向的路径,于是自己狂写,最后写道一百多行,发现逗逼了一回,是无向图,于是改用并查集(来判断是否有环),最后只剩下求最长路劲了,其实对于这样一个没有方向的图,我们可以去等效于一个链子,只需要找到那些链子的头,然后对于这些头每一个dfs(当然可以去剪纸),最后就可以得到我们要求的了.......

代码:

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cstdlib>
 4 #include<iostream>
 5 #include<vector>
 6 #include<algorithm>
 7 //#pragma comment(linker, "/STACK:36777216,36777216")
 8 using namespace std;
 9 const int maxn=100005;
10 int father[maxn];
11 bool vis[maxn];
12 int indeg[maxn];
13 int ans,n,m;
14 struct no
15 {
16   int next;
17   int sum;
18 };
19
20 vector<no>tree[maxn];
21
22 void init(int n){
23     ans=-1;
24     tree[0].clear();
25   for(int i=1;i<=n;i++){
26        father[i]=i;
27        tree[i].clear();
28   }
29   memset(vis,0,sizeof(vis));
30   memset(indeg,0,sizeof(int)*(n+1));
31 }
32
33 int find(int a)
34 {
35    while(a!=father[a])
36      a=father[a];
37     return a;
38 }
39 void dfs(int pos,int res)
40 {
41      ans=max(ans,res);
42   int len=tree[pos].size();
43     for(int i=0;i<len;i++)
44     {
45       if(vis[tree[pos][i].next]==0)
46       {
47        vis[tree[pos][i].next]=1;
48        dfs(tree[pos][i].next,res+tree[pos][i].sum);
49        vis[tree[pos][i].next]=0;
50       }
51   }
52 }
53
54 int main()
55 {
56   int i,x,y,aa,bb,cc;
57   bool flag;
58   while(scanf("%d%d",&n,&m)!=EOF)
59   {
60       init(n);
61       flag=0;
62       for(i=1;i<=m;i++){
63       scanf("%d%d%d",&aa,&bb,&cc);
64       indeg[aa]++;
65       indeg[bb]++;
66       tree[aa].push_back((no){bb,cc});   //无向图
67       tree[bb].push_back((no){aa,cc});
68      if(!flag){
69        x=find(aa);
70        y=find(bb);
71       if(x==y) flag=1;
72       else father[y]=x;
73      }
74       }
75       if(flag)printf("YES\n");
76       else{
77          //寻找端点
78           for(int i=1;i<=n;i++)  {
79             if(indeg[i]==1)
80              tree[0].push_back((no){i,0});   //将多源汇集到一点
81           }
82           vis[0]=1;
83         dfs(0,0);
84         printf("%d\n",ans);
85       }
86   }
87  return 0;
88 }

Similar Posts:

  • HDU 4514 湫湫系列故事——设计风景线(并查集+树的直径)

    题目链接: HDU 4514 湫湫系列故事--设计风景线 题意: n个点和m条无向边.先判环,无环的话输出最长直径. 数据范围:n≤105,m≤106 分析: 并查集判环,树的直径两遍dfs即可. 用C++交AC,G++就MLE,o(╯□╰)o //#pragma comment(linker,"/STACK:102400000, 102400000") #include <stdio.h> #include <string.h> #include <al

  • 【HDU】4514 - 湫湫系列故事——设计风景线(树的直径 &amp; 并查集 &amp; dfs)

    点击打开题目 湫湫系列故事--设计风景线 Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others) Total Submission(s): 4005    Accepted Submission(s): 716 Problem Description 随着杭州西湖的知名度的进一步提升,园林规划专家湫湫希望设计出一条新的经典观光线路,根据老板马小腾的指示,新的风景线最好能建成环形,如果没

  • HDU 4514 湫湫系列故事——设计风景线 (树的直径+并查集)

    湫湫系列故事--设计风景线 Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others) Total Submission(s): 4130    Accepted Submission(s): 727 Problem Description 随着杭州西湖的知名度的进一步提升,园林规划专家湫湫希望设计出一条新的经典观光线路,根据老板马小腾的指示,新的风景线最好能建成环形,如果没有条件建成环形

  • hdu 4514 湫湫系列故事——设计风景线(dfs)

    小记: 最开始读不懂题,然后看了下discuss里,原来是求判环,若没环则求森林里的树的最长直径(后来才知道一棵树里距离最远的两点的距离叫树的直径),看了之后,最开始想到了并查集判环,但是后面想不到如果求树的最长直径了,于是沉思良久,dfs可以做到. 思路:对于dfs的某一点,我们保存它两个数据,因为是一棵树,所以对于其中一个点,以它为起点,dfs的某两个终点,通过这个起点,这一条路径就是以该起点为根节点的树的最长直径, 这样dfs所有节点,最后得到的最长直径 就是answer了.搜i时,以i为

  • 树形dp hdu-4514 湫湫系列故事——设计风景线

    题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=4514 题目意思: 给你一张图,让你判断图中是否有环,如果没环求出最长的路径. 解题思路: 用dfs判断是否有环,再用两次dfs求出树上的最长路了(树的直径). 这里用到了一个树的性质,从树上的任意节点出发找到的最长路端点一定是该树直径的端点.证明请看这篇:http://www.haogongju.net/art/1384945 代码: #pragma comment(linker, "/STACK

  • HDU - 4507 吉哥系列故事——恨7不成妻 (数位DP&amp;记忆化dfs)好题

    HDU - 4507 吉哥系列故事--恨7不成妻 Time Limit:                                                        500MS                          Memory Limit:                                                        32768KB                          64bit IO Format:         

  • HDU:小Q系列故事——为什么时光不能倒流

    http://acm.hdu.edu.cn/showproblem.php?pid=4510 小Q系列故事--为什么时光不能倒流 Time Limit: 300/100 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others) Total Submission(s): 2723 Accepted Submission(s): 1189 Problem Description 我以为我会是最坚强的那一个 我还是高估了自己 我以为你会是最无

  • hdu 4512 吉哥系列故事——完美队形I(最长公共上升序列)

    吉哥系列故事--完美队形I Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others) Total Submission(s): 587 Accepted Submission(s): 130 Problem Description 吉哥这几天对队形比较感兴趣. 有一天,有n个人按顺序站在他的面前,他们的身高分别是h[1], h[2] ... h[n],吉哥希望从中挑出一些人,让这些人形成一个新

  • hdu 4501 小明系列故事——买年货(多维背包)

    小明系列故事--买年货 Time Limit: 5000/2000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others) Total Submission(s): 831 Accepted Submission(s): 335 Problem Description 春节将至,小明要去超市购置年货,于是小明去了自己经常去的都尚超市. 刚到超市,小明就发现超市门口聚集一堆人.用白云女士的话说就是:"那家伙,那场面,真是人山人海,锣鼓喧

  • hdu 4512 吉哥系列故事——完美队形I(LICS)

    吉哥系列故事--完美队形I Problem Description 吉哥这几天对队形比较感兴趣. 有一天,有n个人按顺序站在他的面前,他们的身高分别是h[1], h[2] ... h[n],吉哥希望从中挑出一些人,让这些人形成一个新的队形,新的队形若满足以下三点要求,则称之为完美队形: 1.挑出的人保持他们在原队形的相对顺序不变: 2.左右对称,假设有m个人形成新的队形,则第1个人和第m个人身高相同,第2个人和第m-1个人身高相同,依此类推,当然,如果m是奇数,中间那个人可以任意: 3.从左到中

Tags: