首页 > 代码库 > 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

3 3 1 2 1 2 3 1 3 1 1
 

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 湫湫系列故事――设计风景线