ACM-ICPC Live Archive 6039 Let's Go Green

本文从WordPress迁移而来, 查看全部WordPress迁移文章

数据结构 树 dp

题意:给出一棵无根树,每条边有边权,意思是允许多少辆单车通过。单车在树上走,不要不走回头路(即一条边不能走两次),怎么走都行,没走过一条边,就相当于好掉了一条边的1个权。所以它问的的是,要耗掉整棵树的边权,最少只需要多少单车。(肯定就不是所有边权相加了,因为一辆单车可以走几条边,被它经过都能)

在别人的指导下明白了这题的亮点是摆脱掉边,用点来思考。走过边,其实也就是走过了点

对于一个点它的所有边,用w1,w2,w3….wm,并且约定w1是最大权值那条。我们求出这些边和

sum = w1+w2+w3+w4…..+wm

然后判断

  1. w1 >= sum - w1 , 也就是最大边权大于其他所有边权的和,那么就可以安排w1个单车经过这条边走向u,然后在u这里分流,因为w1大于其余所有边的和,所以w1个单车能全部分流满所有边,并且还有剩余,剩余的那就停住了
  2. w1 < sum - w1 , 那么是不是要安排sum - w1辆单车呢?不是的,是安排(sum + 1)/2辆单车。从w1派出单车到达u点,然后分流到其他边,还有一些边权没有被填满,那么就在剩余的边权中取下一半,然后这1半又能去到剩余的那一半,所以总共派出的单车刚好是总数的一半
  3. 其余部分是递归的,算出每个点,它下面的子树,如果要填满需要多少花费,然后再加上自己的,也就是上面计算的。但是这样计算时有重复的,dfs过程中,父边被重复覆盖要减去
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define N 100010
#define INF 0x3f3f3f3f
#define cl memset
#define ll long long

int n,tot,head[N];
struct edge{
int v,w,next;
}e[2*N];

inline void add(int u ,int v,int w){
e[tot].v = v; e[tot].w = w;
e[tot].next = head[u]; head[u] = tot++;
}

int dfs(int u ,int fa ,int inw){
int res = 0 , maxw = -INF , sum = 0;
bool leaf = true;
for(int k = head[u]; k != -1; k = e[k].next)
if(fa != e[k].v){
leaf = false;
int v = e[k].v , w = e[k].w;
maxw = max(maxw , w);
sum += w;
res += dfs(v,u,w);
}
maxw = max(maxw , inw);
sum += inw;
if(!leaf){
res -= inw;
if(maxw >= sum - maxw)
res += maxw;
else
res += ((sum+1) >> 1);
}
return res;
}

int main(){
int cas;
scanf("%d",&cas);
for(int c = 1; c <= cas; c++){
tot = 0;
cl(head,-1,sizeof(head));
scanf("%d",&n);
for(int i = 1; i < n; i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);
add(v,u,w);
}
int res = dfs(1,-1,0);
printf("Case #%d: %d\n",c,res);
}
return 0;
}