首页 > 代码库 > HDU 4514 湫湫系列故事——设计风景线（并查集+树形DP）
HDU 4514 湫湫系列故事——设计风景线（并查集+树形DP）
湫湫系列故事——设计风景线
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 4669 Accepted Submission(s): 853
Problem Description
随着杭州西湖的知名度的进一步提升，园林规划专家湫湫希望设计出一条新的经典观光线路，根据老板马小腾的指示，新的风景线最好能建成环形，如果没有条件建成环形，那就建的越长越好。
现在已经勘探确定了n个位置可以用来建设，在它们之间也勘探确定了m条可以设计的路线以及他们的长度。请问是否能够建成环形的风景线？如果不能，风景线最长能够达到多少？
其中，可以兴建的路线均是双向的，他们之间的长度均大于0。
现在已经勘探确定了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
接下去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
题目链接：HDU 4514
对于有圈的情况，在输入的时候直接用并查集判断即可，对于求图的最长路，以前是用一次DFS后再从最大长度点BFS，到这题就直接超时了……于是去膜了一下树形DP的解法，对于任意一个点U所在其下的子图G均可以求其中最长路与次长路，相加为G中最长路，显然最长路有一个最优子结构性质：当前点U的最长路一定是邻接点V的最长路加上当前到邻接点的长度，为什么？如果把U当作转折点，把其他路平均地“折”到U的左边和右边，那就是左边的最远点到右边的最远点的距离，显然左右两边的最远点在整个图里来说一个将成为最远点，一个成为次远点，这样以来便可以用DFS解决，题目所给的无向图好像肯能不是一个联通图，而是多个连通分量，搜索的时候用vis标记一下就好了
代码：
#include <stdio.h>#include <iostream>#include <algorithm>#include <cstdlib>#include <sstream>#include <numeric>#include <cstring>#include <bitset>#include <string>#include <deque>#include <stack>#include <cmath>#include <queue>#include <set>#include <map>using namespace std;#define INF 0x3f3f3f3f#define LC(x) (x<<1)#define RC(x) ((x<<1)+1)#define MID(x,y) ((x+y)>>1)#define CLR(arr,val) memset(arr,val,sizeof(arr))#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);typedef pair<int, int> pii;typedef long long LL;const double PI = acos(-1.0);const int N = 100010;const int M = 1000010;struct edge{ int to, nxt, dx; edge() {} edge(int To, int Nxt, int Dx): to(To), nxt(Nxt), dx(Dx) {}};edge E[M << 1];int head[N], tot;int dp[N][2];int pre[N];bitset<N>vis;void init(){ CLR(head, -1); tot = 0; CLR(dp, 0); CLR(pre, -1); vis.reset();}int Find(int n){ if (pre[n] == -1) return n; return pre[n] = Find(pre[n]);}bool joint(int a, int b){ a = Find(a), b = Find(b); if (a == b) return false; pre[a] = b; return true;}inline void add(int s, int t, int d){ E[tot] = edge(t, head[s], d); head[s] = tot++;}void dfs(const int &u, const int &pre){ vis[u] = true; for (int i = head[u]; ~i; i = E[i].nxt) { int v = E[i].to; if (v != pre) { dfs(v, u); int temp = dp[v][0] + E[i].dx; if (temp > dp[u][0]) { dp[u][1] = dp[u][0]; dp[u][0] = temp; } else if (temp > dp[u][1]) dp[u][1] = temp; } }}int main(void){ int n, m, a, b, c, i; while (~scanf("%d%d", &n, &m)) { init(); bool ok = true; for (i = 0; i < m; ++i) { scanf("%d%d%d", &a, &b, &c); add(a, b, c); add(b, a, c); if (!joint(a, b)) ok = false; } if (!ok) puts("YES"); else { for (i = 1; i <= n; ++i) if (!vis[i]) dfs(i, -1); int ans = -INF; for (i = 1; i <= n; ++i) if (dp[i][0] + dp[i][1] > ans) ans = dp[i][0] + dp[i][1]; printf("%d\n", ans); } } return 0;}HDU 4514 湫湫系列故事——设计风景线（并查集+树形DP）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。