HDU-4514 湫湫系列故事——设计风景线 手动扩栈

题意：给定一个无向图，首先判定是否成环，然后求一条最长链。

分析：成环用并查集，最长链就是个最简单的树形dp了。

#include <cstdlib>

#include <cstring>

#include <cstdio>

#include <algorithm>

#include <vector>

#pragma comment(linker, "/STACK:1024000000,1024000000")

using namespace std;

const int N = ;

int n, m, ans;

int set[N];

int dp[N];

struct Edge {

    int v, f;

    Edge() {}

    Edge(int _v, int _f) : v(_v), f(_f) {}

};

vector<Edge>vt[N];

int find(int x) {

    return x == set[x] ? x : x = find(set[x]);

}

void dfs(int p, int u) {

    int forkmax = ;

    for (int i = ; i < (int)vt[u].size(); ++i) {

        int v = vt[u][i].v, f = vt[u][i].f;

        if (v == p) continue;

        dfs(u, v);

        ans = max(ans, dp[v]+f+forkmax);

        forkmax = max(forkmax, dp[v] + f);

    }

    dp[u] = forkmax;

}

/*

6 4

1 2 2

1 3 4

4 5 4

4 6 3

*/

void solve() {

    for (int i = ; i <= n; ++i) {

        if (dp[i] == -) dfs(, i);

    }

    printf("%d\n", ans);

}

int main() {

    while (scanf("%d %d", &n, &m) != EOF) {

        int a, b, c, x, y;

        bool loop = false;

        ans = ;

        for (int i = ; i <= n; ++i) {

            dp[i] = -;

            set[i] = i;

            vt[i].clear();

        }

        for (int i = ; i < m; ++i) {

            scanf("%d %d %d", &a, &b, &c);

            if (loop) continue;

            x = find(a), y = find(b);

            if (x != y) set[x] = y;

            else loop = true;

            vt[a].push_back(Edge(b, c));

            vt[b].push_back(Edge(a, c));

        }

        if (loop) {

            puts("YES");

            continue;

        }

        solve();

    }

    return ;

}