Luogu P1453 城市环路(基环树DP)

法一：dsu

#include <bits/stdc++.h>

    using ll = long long;
    using namespace std;

    const int N = 100010;

    struct node {
        int v, nxt;
    }e[N * 2];

    int h[N], idx;
    int p[N], n, w[N];
    int dp[N][2];

    inline void add(int u, int v) {
        e[++idx] = {v, h[u]}, h[u] = idx;
    }

    int find(int x) {
        return x == p[x] ? p[x] : p[x] = find(p[x]);
    }

    void dfs(int u, int fa) {
        std::cerr << u << " " << fa << "\n";
        dp[u][1] = w[u], dp[u][0] = 0;
        for (int i = h[u]; i; i = e[i].nxt) {
            int v = e[i].v;
            if (v == fa) continue;
            dfs(v, u);
            dp[u][1] += dp[v][0];
            dp[u][0] += std::max(dp[v][0], dp[v][1]);
        }
    }

    signed main() {
        std::cin.tie(nullptr)->sync_with_stdio(false);

        cin >> n;
        for (int i = 1; i <= n; i++) {
            std::cin >> w[i];
            p[i] = i;
        }

        int s, t;

        for (int i = 1; i <= n; i++) {
            int u, v;
            std::cin >> u >> v;
            u++, v++;
            if (find(u) == find(v)) {
                s = u;
                t = v;
                continue;
            }
            add(u, v), add(v, u);
            p[find(u)] = find(v);
        }

        double k;
        cin >> k;

        int ans = 0;
        // cerr << ans << " " << s << ' ' << t << "\n";
        dfs(s, 0); ans = dp[s][0];
        dfs(t, 0); ans = max(ans, dp[t][0]);

        // printf("%.1lf\n", ans * k);
        cout << fixed << setprecision(1) << ans * k << "\n";

       return 0 ^ 0;
    }

基环树 + dp

#include <bits/stdc++.h>

    using ll = long long;
    using namespace std;

    const int N = 100010;
    const int inf = 0x3f3f3f3f;

    struct node {
        int v, nxt;
    }e[N * 2];

    int h[N], idx, n, b;
    int a[N], d[N];
    int c[N], ptr;
    bool cir[N];
    int dp[N][2], ndp[N][2];

    void add(int u, int v) {
        e[++idx] = {v, h[u]}, h[u] = idx;
    }

    void dfs1(int u, int fa) {
        for (int i = h[u]; i; i = e[i].nxt) {
            int v = e[i].v;
            if (v == fa || cir[v]) continue;
            if (d[v] == 2) {
                c[++ptr] = v, cir[v] = true;
                dfs1(v, u);
                break;
            }
        }
    }

    void dfs(int u, int fa) {
        dp[u][1] = a[u];
        for (int i = h[u]; i; i = e[i].nxt) {
            int v = e[i].v;
            if (v == fa || cir[v]) continue;
            dfs(v, u);
            dp[u][0] += max(dp[v][0], dp[v][1]);
            dp[u][1] += dp[v][0];
        }
    }

    signed main() {
        std::cin.tie(nullptr)->sync_with_stdio(false);

        cin >> n;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
        }

        for (int i = 1; i <= n; i++) {
            int u, v;
            cin >> u >> v;
            u++, v++;
            d[u]++, d[v]++;
            add(u, v), add(v, u);
        }

        double k;
        cin >> k;
        
        queue<int> q;
        for (int i = 1; i <= n; i++) 
            if (d[i] == 1) 
                q.push(i);

        while(q.size()) {
            int u = q.front();
            q.pop();
            for (int i = h[u]; i; i = e[i].nxt) {
                int v = e[i].v;
                if (--d[v] == 1) 
                    q.push(v);
            }
        }  

        for (int i = 1; i <= n; i++) {
            if (d[i] == 2) {
                c[++ptr] = i, cir[i] = true;
                dfs1(i, 0);
                break;
            }
        }

        for (int i = 1; i <= ptr; i++) {
            dfs(c[i], 0);
        }

        for (int i = 0; i <= n; i++) {
            ndp[i][0] = ndp[i][1] = -inf;
        }

        ndp[1][0] = dp[c[1]][0];
        for (int i = 2; i <= ptr; i++) {
            ndp[i][1] = ndp[i - 1][0] + dp[c[i]][1];
            ndp[i][0] = max(ndp[i - 1][0], ndp[i - 1][1]) + dp[c[i]][0];
        }

        int ans = max(ndp[ptr][0], ndp[ptr][1]);

        for (int i = 0; i <= n; i++) {
            ndp[i][0] = ndp[i][1] = -inf;
        }

        ndp[1][1] = dp[c[1]][1];
        for (int i = 2; i <= ptr; i++) {
            ndp[i][1] = ndp[i - 1][0] + dp[c[i]][1];
            ndp[i][0] = max(ndp[i - 1][0], ndp[i - 1][1]) + dp[c[i]][0];
        }

        ans = max(ans, ndp[ptr][0]);

        cout << fixed << setprecision(1) << k * ans << "\n";
        return 0 ^ 0;
    }

原文地址：http://www.cnblogs.com/Haven-/p/16919581.html