锐客网

  1. 首页 > it技术 > >

ZOJ 4031 Game on a Tree 树形DP

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5772
BaoBao is playing a game on a rooted tree with vertices and weighted edges. At the beginning of the game, a chess piece is placed on the root of the tree, which is vertex 1.
In each step, BaoBao can perform one of the four operations:
Move the chess piece along an edge from its current vertex to a child vertex. This operation will cost BaoBao units of value, where is the weight of the edge.
Jump the chess piece back to vertex 1. This operation is free and won’t cost BaoBao any unit of value.
Set a “save point” on the current vertex of the chess piece. If a save point has been set on some other vertex before, the save point on the old vertex will be removed (so there will be at most one save point on the tree at the same time). This operation is free and won’t cost BaoBao any unit of value.
Jump the chess piece back to the save point (the save point must be set before this operation). This operation is free and won’t cost BaoBao any unit of value.
The goal of the game is to visit every leaf vertex of the tree using the chess piece. Please help BaoBao calculate the minimum units of value he has to spend to achieve the goal.
Recall that a leaf vertex of a tree is a vertex with no child.
Input
There are multiple test cases. The first line of the input contains an integer , indicating the number of test cases. For each test case:
The first line contains one integer (), indicating the size of the tree.
The following lines each contains three integers , and (, ), indicating an edge connecting vertex and vertex with weight in the tree.
【ZOJ 4031 Game on a Tree 树形DP】It’s guaranteed that the given graph is a tree, and the sum of over all test cases will not exceed 2000.
Output
For each test case output one line containing one integer, indicating the minimum units of value BaoBao has to spend to achieve the goal.
Sample Input
3
8
1 2 1
3 1 1
2 4 2
5 4 2
6 2 2
3 7 3
8 3 3
8
1 2 1
2 3 1
3 4 1
3 5 1
2 6 1
6 7 1
6 8 1
8
1 2 100
2 3 1
3 4 1
3 5 1
2 6 1
6 7 1
6 8 1
Sample Output
14
8
107
题意 ：
给出一颗一1号节点为根节点的树，给出四种操作，分别为：
1。 从父亲节点走向儿子节点
2。跳回一号起点
3。将当前结点设置为存档点，存档点在同一时刻只能存在一个
4。跳回存档点
一号操作会增加等价于边权的花费 2，3，4无花费 问遍历所有叶子结点的最小花费。
一看就应该往树形DP上想，
由于结点数很小 只有200 可以做n^2的DP

建立两个dp,一个二维，第一维表示在哪个节点，第二维表示传送点放在哪个节点，另一个dp数组表示父节点没有传送点时的最小花费
当然 也有O(n)的解法
本来是想定义每个节点是否作为存档点来进行DP的 后来发现有点麻烦。。。 转移不出来。 就往其他方面去想。
可以按照下一步状态来进行DP，对于每个节点 我们只有当遍历完他所有子节点后才会考虑跳到另一颗子树上。
所以可以有如下定义：
定义DP[cur][0/1] 表示遍历cur节点的子树叶子节点，1表示返回该cur 0表示不返回cur.
那么对于当前节点cur就有两种转移方式 。
1。 遍历完一颗子树后， 跳到1号结点 然后再走到cur
2。 讲cur设置为存档点，遍历完子树后直接进行4操作跳回cur
这样就可求出所有遍历完子树后返回cur的最优方案。
而不返回cur节点的方案可以通过贪心的思想求出，只要找出最长链并减去就是不返回cur节点的最佳法案了。
复杂度O(n)
看错题目了，以为可以从子节点回到父节点 找了好久BUG。。。。 。。。 5/8号更新。。
过一天回头来看这道题 ，发现自己还是没能理解这种O(n)的写法，于是又写了一晚上。。。
由于定义的状态是遍历完一颗子树返不返回当前节点 ，所以子树与子树之间是相互独立的，互不干扰（既 不存在存档点设置互相矛盾的问题）。
再来看状态转移，
if(dis[v]+dp[v][0]

对于dp[cur][1 ]这个状态的转移可以做如下思考：
回到cur节点的方法有两种
1。 将cur节点设置为存档点 2。 遍历完子树后 返回1节点 再走到cur节点。
状态其实是有单调性的 在节点深度高的时候 会一直选择将cur节点设置为存档点，之后会一直是跳转到1号节点再转到当前cur节点 （maybe）
现在考虑不回到cur 的情况，对于每次要回到cur 都有一个>=0的额外的花费 cost， 所以 现在只要找到这个最大cost就行了
dp[cur][0]=dp[cur][1]-MAX(cost);
对于遍历每颗子树的额外cost也很好求。 将cost初始化为0 对于每颗子树 如果遍历完后，选择不回到cur节点的话，
那么他的花费必定就是edge[i].w+dp[v][0 ] 将其减去 就是额外的cost。。。。
md 题目没想清楚就写题解真的是太脑残了。。。。
#include #include #include #include #include #include #include #include #include using namespace std; typedef long long LL; LL dp[205][2]; // 定义DP[cur][0/1] 表示遍历cur节点的子树叶子节点，1表示返回该cur 0表示不返回cur. const int MAX=1e3+10; class Edge{ public: LL u,v,next,w; }; int tot=0; Edge edge[MAX]; int head[MAX]; void add(LL u,LL v,LL w){ edge[tot].u=u; edge[tot].v=v; edge[tot].w=w; edge[tot].next=head[u]; head[u]=tot++; } LL sizes[MAX]; // 该节点有多少个叶子节点 LL dis[MAX]; // 该1节点到该节点的距离 int du[205]; // 可以表示节点的子节点数 void dfs(int u,int per){ if(du[u]<=1){ sizes[u]=1; }else{ sizes[u]=0; } LL cnt=0; for(int i=head[u]; i!=-1; i=edge[i].next){ int v=edge[i].v; if(v==per) continue; dis[v]=dis[u]+edge[i].w; dfs(v,u); LL val; sizes[u]+=sizes[v]; if(dis[v]+dp[v][0]1]){ val = dis[v]+dp[v][0]; cnt = max(cnt,val-(edge[i].w+dp[v][0])); }else{ val = sizes[v]*edge[i].w+dp[v][1]; cnt = max(cnt,val-(edge[i].w+dp[v][0])); } dp[u][0]+=val; dp[u][1]+=val; } dp[u][0]-=cnt; } int main(){ int T; cin>>T; while(T--){ int n; scanf("%d",&n); memset(dp,0,sizeof dp); memset(head,-1,sizeof head); memset(dis,0,sizeof dis); memset(du,0,sizeof du); memset(sizes,0,sizeof sizes); tot=0; for(int i=1; i

    推荐阅读


    上一篇：js 日期转字符串 时间类型转换

    下一篇：Linux|Linux Shell文本处理命令技巧