HDU 4514 湫湫系列故事——设计风景线（并查集+树形DP）

时间：2023-11-26 09:11:38

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

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。
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

题目链接：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;

}

相关文章