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

本文主要是介绍HDU - 4514 湫湫系列故事――设计风景线，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

Sample Output

  YES 
思路：RE到吐血的地步，HDU竟然有个栈的初始化：#pragma comment(linker, "/STACK:1024000000,1024000000")，一口老血喷出来，首先判断环形：并查集，然后就是树形DP
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
const int maxn = 100005;struct Edge {int v, f;Edge() {}Edge(int v, int f) {this->v = v;this->f = f;}
};
vector<Edge> ve[maxn];
int n, m, ans;
int fa[maxn], dp[maxn];int find(int x) {if (x != fa[x])fa[x] = find(fa[x]);return fa[x];
}void dfs(int p, int u) {int Max = 0;for (int i = 0; i < ve[u].size(); i++) {int v = ve[u][i].v, f = ve[u][i].f;if (v == p)continue;dfs(u, v);ans = max(ans, dp[v] + f + Max); //两条分支和的最大值Max = max(Max, dp[v] + f);}dp[u] = Max;
}void solve() {for (int i = 1; i <= n; i++) if (dp[i] == -1)dfs(0, i);printf("%d\n", ans);
}int main() {int a, b, c, x, y;while (scanf("%d%d", &n, &m) != EOF) {ans = 0;int flag = 0;for (int i = 1; i <= n; i++) {dp[i] = -1;fa[i] = i;ve[i].clear();}for (int i = 0; i < m; i++) {scanf("%d%d%d", &a, &b, &c);if (flag) continue;x = find(a), y = find(b);if (x != y)fa[x] = y;else flag = 1;ve[a].push_back(Edge(b, c));ve[b].push_back(Edge(a, c));}if (flag) {printf("YES\n");continue;}solve();}	return 0;
}

这篇关于HDU - 4514 湫湫系列故事――设计风景线的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！