首页 > 代码库 > 2014 Super Training #9 E Destroy --树的直径+树形DP
2014 Super Training #9 E Destroy --树的直径+树形DP
原题： ZOJ 3684 http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3684
题意： 给你一棵树，树的根是树的中心（到其他点的最远距离最小）。现在你要破坏所有叶子节点到根节点的连通，每条边破坏都需要一定能量。你有一个能量为power的武器，能破坏能量小于等于power的任何路。求最少需要的power。
解法参考博客：http://blog.csdn.net/gzh1992n/article/details/8651191，我也不是很懂，就是先找出树的中心点，然后做树形DP。
还有一种找中点的方法：
从任意点进行第一次dfs求得数的直径的一个端点，从这个端点dfs求得另一个端点，然后遍历直径，找到最接近直径一半的点就是中点。
没试过，博客http://www.cnblogs.com/hundundm/archive/2013/01/21/2870271.html里有提到。
代码：
#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <cstdlib>#include <algorithm>#define ll long longusing namespace std;#define N 10007struct node{ int v,len,power; int next;}G[4*N];const ll Mod = (ll)(1LL<<60);int head[N],tot,n;ll dp[N];int ma[N],sma[N];void addedge(int u,int v,int len,int power){ G[tot].v = v; G[tot].len = len; G[tot].power = power; G[tot].next = head[u]; head[u] = tot++;}void dfs(int u,int fa){ ma[u] = 0; sma[u] = 0; for(int i=head[u];i!=-1;i=G[i].next) { int v = G[i].v; if(v == fa) continue; dfs(v,u); int L = ma[v]+G[i].len; if(ma[u] < L) // sma[u] < ma[u] < L { sma[u] = ma[u]; ma[u] = L; } else if(sma[u] < L) // sma[u] < L < ma[u] sma[u] = L; }}void DP(int u,int fa){ for(int i=head[u];i!=-1;i=G[i].next) { int v = G[i].v; if(v == fa) continue; if(ma[u] == ma[v]+G[i].len) //最远的点在v的子树内 { ma[v] = max(ma[v],sma[u]+G[i].len); sma[v] = max(sma[v],sma[u]+G[i].len); } else { ma[v] = max(ma[v],ma[u]+G[i].len); sma[v] = max(sma[v],ma[u]+G[i].len); } DP(v,u); }}int findCenter(){ dfs(1,0); DP(1,0); int cen = min_element(ma+1,ma+n+1)-ma; return cen;}void dfs2(int u,int fa){ int flag = 0; ll power = 0; dp[u] = Mod; for(int i=head[u];i!=-1;i=G[i].next) { int v = G[i].v; if(v == fa) continue; dfs2(v,u); power = max(power,min(dp[v],(ll)G[i].power)); flag = 1; //不是叶子节点 } if(flag) dp[u] = power;}ll Get(int cen){ dfs2(cen,0); return dp[cen];}int main(){ int u,v,len,power; int cen,i; while(scanf("%d",&n)!=EOF) { memset(head,-1,sizeof(head)); tot = 0; for(i=0;i<n-1;i++) { scanf("%d%d%d%d",&u,&v,&len,&power); addedge(u,v,len,power); addedge(v,u,len,power); } cen = findCenter(); printf("%lld\n",Get(cen)); } return 0;}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。