题解：P10418 [蓝桥杯 2023 国 A] 相连的边

Joww · 2024-09-24 16:37:02 · 题解

由于题目给定一棵树，因此相连通的三条边要么是链，要么是菊花。

菊花比较简单，做法是——

• 枚举菊花的中心结点 i，
• 取出结点 i 的三条边权最大的邻接边，
• 此时这三条边就是以结点 i 为中心且边权和最大的三条边组成的菊花。

对于链，每条链最特殊的边是位于中间的那条，所以做法是——

• 枚举链的中心边 (i, x)（边权为 y），记为①边；
• 取出 i 的、不与 x 相连的、边权最大的邻接边，记为②边；
• 取出 x 的、不与 i 相连的、边权最大的邻接边，记为③边；
• 【①、②、③】就是以①边为中心边且边权和最大的三条边组成的链。

因此，影响答案的只有每个点边权最大的三条邻接边，预处理后朴素地枚举即可。

为了实现方便，以下代码使用了 sort，但实际上可以使用循环在 O(n) 内找出边权最大的三条边。

#include <bits/stdc++.h>
using namespace std;

const int N = (int) 2e5 + 10;
vector<pair<int, int>> g[N];

int main() {
    int n;
    cin >> n;
    for (int i = 2; i <= n; i++) {
        int x, y;
        cin >> x >> y;
        g[i].push_back({ y, x });
        g[x].push_back({ y, i });
    }

    long long ans = 0;

    // type1 : flower
    for (int i = 1; i <= n; i++) {
        sort(g[i].begin(), g[i].end(), greater<pair<int, int>>());
        if (g[i].size() >= 3) {
            ans = max(ans, 0ll + g[i][0].first + g[i][1].first + g[i][2].first);
        }
    }

    // type2 : chain
    for (int i = 1; i <= n; i++) {
        if (g[i].size() == 1) continue;
        for (auto [y, x] : g[i]) {
            if (g[x].size() == 1) continue;
            long long sum = y;
            sum += (g[x][0].second != i ? g[x][0] : g[x][1]).first;
            sum += (g[i][0].second != x ? g[i][0] : g[i][1]).first;
            ans = max(ans, sum);
        }
    }
    cout << ans << '\n';

    return 0;
}

Bonus: 如果题目给定的不是树，而是一张图，又该怎么做呢？