思路
这题是树形$DP$。
附上我的图:
这题没有让我们求回到根节点的距离最小值,这里只需要一些变换即可:
我们的图从$1–2–4–2–5–2–1–3$,这里大家可以发现,每一条边都会遍历到两遍,但是回到根节点的那条路径不用算,因此我们要减去最长路,才能使答案最优,所以我们的答案是$\sum_\limits{i=1}^{m}w_i-\max\limits_{i=1}^{n}\lbrace d_i\rbrace$。
代码
删去了无用信息。
#include <iostream>
#include <cstring>
using namespace std;
typedef long long LL;
const int N = 100010,M = 2 * N;
int n;
int h[N],e[M],w[M],ne[M],idx; //链式前向星
LL d[N]; //开long long
void add (int a,int b,int c) {
e[idx] = b;
w[idx] = c;
ne[idx] = h[a];
h[a] = idx++;
}
void get_dis (int x,int fa,int c) { //算出距离,这里加fa是防止搜回父节点
d[x] = d[fa] + c;
for (int i = h[x];~i;i = ne[i]) {
int j = e[i];
if (j == fa) continue;
get_dis (j,x,w[i]);
}
}
int main () {
memset (h,-1,sizeof (h));
cin >> n;
LL ans = 0; //开long long
for (int i = 1;i <= n - 1;i++) {
int a,b,c;
cin >> a >> b >> c;
ans += c * 2;
add (a,b,c),add (b,a,c);
}
get_dis (1,0,0);
LL maxx = 0;
for (int i = 1;i <= n;i++) maxx = max (maxx,d[i]);
cout << ans - maxx << endl;
return 0;
}
请问h[N],e[M],w[M],ne[M] 这些数组都是存的什么数据啊。。。实在看不懂
建议学一下链式前向星
这对数组合起来就是链式前向星
感谢大佬,这就去
ok
oi爷能告诉我你这是用什么画的图吗
就用win10的画图
这tm题简单了,这服务器倒是1天崩1次
addd
否则能10-名
否则我丢掉的50分钟就回来了
addd
同为小六的我看到这题就直呼简单
@[mp4]我小号
雀实简单
知道
addd
感觉现在周赛题变水了
adddd
很简单,都可以AK
这是小号
您真的是小学六年级吗
对啊,咋了
这题不是很简单吗???
做的题多了就有感觉了
同为小六的我自愧不如
我也很弱的
才学了2years
我也小六
我也是做题多了就有感觉,4622和4706上来就有感觉
addd