生命之源
难度:
时间限制: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;
}