题目传送门

sol:看了题意显然是最大生成树，但是任意两个点之间都有边，大概有n*n条边。用朴素的最小生成树算法显然不行。联想了一下树的直径还是不会。看了大佬的题解，懂了。。。

所以还是直接贴大佬博客链接好了：https://blog.csdn.net/yasola/article/details/72229734

树的直径

#include "bits/stdc++.h"

using namespace std;

typedef long long LL;

typedef pair<int, int> PII;

typedef pair<int, LL> PIL;

const int MAXN = 1e5 + ;

vector<PII> edge[MAXN];

LL _max; int nn1, nn2;

LL dis[MAXN];

PIL get_diameter(int rt, int fa) {

    LL m1 = , m2 = ;

    int n1 = rt, n2 = rt;

    for (PII i : edge[rt]) {

        if (i.first == fa) continue;

        PIL p = get_diameter(i.first, rt);

        if (p.second + i.second > m1) {

            m2 = m1, n2 = n1;

            m1 = p.second + i.second;

            n1 = p.first;

        } else if (p.second + i.second > m2) {

            m2 = p.second + i.second;

            n2 = p.first;

        }

    }

    if (m1 + m2 > _max) {

        nn1 = n1, nn2 = n2;

        _max = m1 + m2;

    }

    return {n1, m1};

}

void dfs(int rt, int fa, LL mm) {

    dis[rt] = max(dis[rt], mm);

    for (PII i : edge[rt]) {

        if (i.first == fa) continue;

        dfs(i.first, rt, mm + i.second);

    }

}

int main() {

    int n;

    while (~scanf("%d", &n)) {

        memset(dis, -, sizeof(dis));

        for (int i = ; i <= n; i++) edge[i].clear();

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

            int u, v, w;

            scanf("%d%d%d", &u, &v, &w);

            edge[u].push_back({v, w});

            edge[v].push_back({u, w});

        }

        _max = -;

        get_diameter(, -);    // 求出树的直径，以及两个端点；

        dfs(nn1, -, ), dfs(nn2, -, );

        LL sum = ;

        for (int i = ; i <= n; i++) sum += dis[i];

        printf("%lld\n", sum - _max);    // 将两个端点加入集合只用算一次直径，而上面的循环算了两次，所以减掉一个直径；

    }

    return ;

}

巴特西

牛客-Highway

题目传送门

最新文章

热门文章