C++问题:魔法王国中有一棵存活千年的古树,由于长时间缺水,它的生命已经岌岌可危。

生命之源
难度:
时间限制:1s
内存限制:128M
开始编程
【题目描述】
魔法王国中有一棵存活千年的古树,由于长时间缺水,它的生命已经岌岌可危。
魔法王国的国王为了保住古树的性命,决定派遣水精灵去滋润它。与一般的树相似,古树有n个结点,其中根结点为1号结点。古树内部由n−1条边相连,由三元组(u
i

,v
i

,d
i

)描述,表示结点u
i

与结点v
i

存在一条长度为d
i

的无向边。
水精灵将会从古树的根结点出发,她每分钟只能走一个单位的距离。从水精灵到达根结点开始计时,她将水送到i号结点的时间称为i号结点的时间称为i号结点的干枯值。

水精灵希望规划一条合理的送水路线,滋润所有的结点并使得所有结点的干枯值总和最小。请帮助水精灵求出干枯值总和的最小值。
【输入格式】
输入共n行:
第一行,一个正整数n,表示古树结点的数量。
接下来n−1行,每行三个正整数u
i

,v
i

,d
i

,表示u
i

号结点与v
i

号结点间存在一条长度为d
i

的无向边。
保证水精灵可以到达所有的结点。
【输出格式】
输出仅一行,一个整数,表示干枯值总和的最小值。
【输入输出样例#1】
输入#1
4
1 2 2
1 3 5
2 4 2
复制
输出#1
19
复制
【数据范围】
对于30%的数据,所有树边的权值为1。
另外40%的数据,保证给定的树是一棵二叉树。
对于100%的数据,1≤n≤2×10
5
,1≤u
i

,v
i

≤n,1≤d
i

≤500。

这个就是典型的哈夫曼树
https://blog.csdn.net/qq_29519041/article/details/81428934


#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
int head[N],ne[N],e[N],w[N],tot,cnt;
int head1[N],ne1[N],e1[N],w1[N],tot1;
int n,d1[N],d2[N],couts,cout1s;
void add(int a,int b,int c){
    e[++tot]=b,w[tot]=c,ne[tot]=head[a],head[a]=tot;
}
void add1(int a,int b,int c){
    e1[++tot1]=b,w1[tot1]=c,ne1[tot1]=head1[a],head1[a]=tot1;
}
void dfs(int u,int fa){
    for (int i = head[u]; i ; i=ne[i]){
        int v=e[i];
        if (v==fa)continue;
        dfs(v,u);
        d1[u]=max(d1[u],d1[v]+w[i]);
    }
    for(int i=head[u];i;i=ne[i]){
        int v=e[i];
        if(v==fa)continue;
        int tmp=d1[v]+w[i];
        for(int j=head[u];j;j=ne[j]){
            int v1=e[j];
            if(v1==fa||v1==v)continue;
            tmp=max(tmp,d2[v1]+w[j]+d1[v]);
        }
        d2[u]+=tmp;
    }
}
void dfs1(int u,int fa){
    for(int i=head[u];i;i=ne[i]){
        int v=e[i];
        if(v==fa)continue;
        dfs1(v,u);
        add1(u,v,w[i]+d1[v]);
    }
    cnt+=max(d1[u],d2[u]);
    couts+=d1[u];
    cout1s+=d2[u];
}
int main(){
    cin>>n;
    for(int i=1;i<n;i++){
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c),add(b,a,c);
    }
    memset(d1,0,sizeof(d1));
    memset(d2,0,sizeof(d2));
    dfs(1,-1);
    dfs1(1,-1);
    // cout<<"couts= "<<couts<<" cout1s= "<<cout1s<<endl<<"cnt= "<<cnt<<endl;
    cout<<cnt+max(couts,cout1s);
    return 0;
}







你的问题描述不清晰啊,截图看下

由于本题涉及到较为复杂的算法,直接给出完整代码可能对您的学习不利。以下是一份参考代码供您学习参考。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 2e5 + 10, M = N << 1;

int h[N], e[M], ne[M], w[M], idx;
int n;
int dist[N];

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}

void bfs(int u)
{
    queue<int> q;
    memset(dist, 0x3f, sizeof dist);
    q.push(u);
    dist[u] = 0;
    while (q.size())
    {
        auto t = q.front();
        q.pop();
        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                q.push(j);
            }
        }
    }
}

int main()
{
    scanf("%d", &n);
    memset(h, -1, sizeof h);
    for (int i = 0; i < n - 1; i ++ )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c), add(b, a, c);
    }
    bfs(1);
    int res = 0;
    for (int i = 1; i <= n; i ++ ) res += dist[i];
    bfs(max_element(dist + 1, dist + n + 1) - dist);
    for (int i = 1; i <= n; i ++ ) res += dist[i];
    printf("%d\n", res);
    return 0;
}