首页 > 代码库 > HDU - 4514 湫湫系列故事――设计风景线

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

2024-07-24 01:02:50   218人阅读

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


联系
我们