fzu2157（树形dp）
时间：2014-03-29 18:15:34
收藏：0
阅读：399
http://acm.fzu.edu.cn/problem.php?pid=2157
这是一道很水的树形dp吧，本来不想写它的题解的，不过比赛的时候，队友说要我做这个题目，但是由于我感觉另一个题目可以出，而放弃做这个题目.....本来可以多出一道的，结果......以后的比赛中，还是得多多注意这个方面的问题。
题意：给出n个点，每个点都有两种花费，一个是0种花费，一个是1种花费，每两个点相连，边也有花费，是随着点所取话费的种类不同，边的花费也不同，边有四种花费，00，01，10，11 问建成整颗树所需要的最少花费。
思路：dp[i][0]代表当前结点取0种花费时建好以i结点为根节点的最少花费，dp[i][1]代表当前结点取1种花费时建好以i结点为根节点的最少花费，那么有动态转移方程就出来了.......
|
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 |
#include<iostream>#include<cstdio>#include<cstring>#include<vector>#include<algorithm>using
namespace std;#define inf (1<<28)struct
node{ int
k; int
a,b,c,d;};int
s[200005][2],dp[200005][2];int
t[200005][2][2],n;vector<node>vet[200005];void
dfs(int
root){ if(vet[root].size()==0) { dp[root][0]=s[root][0]; dp[root][1]=s[root][1]; return; } dp[root][0]=s[root][0]; dp[root][1]=s[root][1]; for(int
i=0;i<vet[root].size();i++) { node p=vet[root][i]; dfs(p.k); dp[root][0]+=min(dp[p.k][0]+p.a,dp[p.k][1]+p.b); dp[root][1]+=min(dp[p.k][0]+p.c,dp[p.k][1]+p.d); }}int
main(){ int
text; scanf("%d",&text); while(text--) { scanf("%d",&n); for(int
i=1;i<=n;i++) scanf("%d",&s[i][0]); for(int
i=1;i<=n;i++) scanf("%d",&s[i][1]); for(int
i=0;i<=n;i++) { vet[i].clear(); dp[i][0]=dp[i][1]=0; } for(int
i=0;i<n-1;i++) { int
x,y,a,b,c,d; scanf("%d%d%d%d%d%d",&x,&y,&a,&b,&c,&d); node p; p.k=y; p.a=a; p.b=b; p.c=c; p.d=d; vet[x].push_back(p); //t[i][0][0]=a; //t[i][0][1]=b; //t[i][1][0]=c; //t[i][1][1]=d; } dfs(1); printf("%d\n",min(dp[1][0],dp[1][1])); } return
0;} |
原文：http://www.cnblogs.com/ziyi--caolu/p/3632682.html
评论（0）