poj 3585 Accumulation Degree

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

树dp

题意:每条边有容量,任选一个点出发流出去,流到叶子的最大流量是多少

两次dfs

定1为根进行dfs1

dp[u]:不考虑u的祖先部分,从u出发,流遍整个子树,能产生的最大流量

dp[u] = sigma( min(dp[v],w) ); //v是u的儿子,w是u-v的容量,若v为叶子,dp[v] = INF;

dfs2

back[u]:不考虑u的子树,从u出发,往祖先方向,流遍所有节点,能产生的最大流量

首先u流到fa,一部分是fa继续向祖先方向流动,一部分是fa流向了非u的儿子节点

back[u] = dp[fa] - min(w,dp[u]) + back[fa]; //w是fa-u的容量

要注意一个特别情况就是一条链的时候

1 - 2 - 3 - 4

单单是上面的计算,所有的back都是0,因为1 - 2那里,

没有考虑一个情况就是1没有其他儿子的,而back[1] = 0;

所以特判一下,if(back[u] = 0) back[u] = cap;

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define N 200010
#define INF 0x3f3f3f3fLL
#define LL long long
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))

int n,tot,head[N];
struct edge{
int u,v,next;
LL w;
edge(){}
edge(int __u,int __v,LL __w){
u = __u; v = __v; w = __w;
}
}e[10*N];

LL dp[N],back[N],ans[N],ANS;

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

void dfs1(int u,int fa){
bool leaf = true;
for(int k = head[u]; k != -1; k = e[k].next){
int v = e[k].v;
LL w = e[k].w;
if(v == fa) continue;
leaf = false;
dfs1(v,u);
dp[u] += min(dp[v],w);
}
if(leaf) dp[u] = INF;
}

void dfs2(int u,int fa,LL cap){
if(fa != -1){
LL tmp = dp[fa] - min(cap,dp[u]);
tmp += back[fa];
back[u] = min(cap,tmp);
if(back[u] == 0) back[u] = cap; //fa = 1,且1只有1个儿子(就是u)的情况
}
bool leaf = true;
for(int k = head[u]; k != -1; k = e[k].next){
int v = e[k].v;
LL w = e[k].w;
if(v == fa) continue;
dfs2(v,u,w);
leaf = false;
}
if(leaf) dp[u] = 0;
ans[u] = back[u] + dp[u];
ANS = max(ANS,ans[u]);
}

int main(){
int T;
scanf("%d",&T);
while(T--){
cl(head,-1); tot = 0;
scanf("%d",&n);
for(int i = 1; i < n; i++){
int u,v; LL w;
scanf("%d%d%lld",&u,&v,&w);
add(u,v,w); add(v,u,w);
}
cl(dp,0); cl(back,0); ANS = 0;
dfs1(1,-1);
dfs2(1,-1,INF);
printf("%lld\n",ANS);
/*
puts("down");
for(int i = 1; i <= n; i++)
printf("%d : %d\n",i,dp[i]);
*/
/*
puts("back");
for(int i = 1; i <= n; i++)
printf("%d : %d\n",i,back[i]);
puts("ans");
for(int i = 1; i <= n; i++)
printf("%d : %d\n",i,ans[i]);
*/
}
return 0;
}