首页 > 代码库 > POJ 1935 树形DP
POJ 1935 树形DP
题目大意:带边权的树,给点一个根,问从根出发遍历某些点,所需的最小花费。
这既然是一棵树,那么从起点k到任意一个的路径都是唯一确定的(这就是树形的好处),我们可以深搜它的孩子,在过程中如果没有要访问的节点就直接返回。
否则将这条路径都标记。而且题目中可知不一定要返回到其实位置,那么可以在某个点停下。
sum[0][u]:回到u点的最短路径
sum[1][u]:不回到u点的最短路径
sum[0][u]+=len*2+sum[0][v]//1 sum[1][u]=min( len+sum[0][u]+sum[1][v], sum[1][u]+sum[0][v]+len*2 )//2第一句很好理解,回到u就是回到v再加上u,v间路径的两倍(来回)
min中1的意思是v之前u的孩子回到u再访问v且不回到u的值,2的意思是先从v出发返回u再访问之前其他的孩子且不回来的值,取最优。
为什么?
因为依题意可知最终只会停到一个点,同时我们要消除访问先后顺序对结果的影响,所以对于v来说可能停到v的子树或u其他孩子的子树中,这个取最优即可。
树形DP就是父节点对孩子节点情况去最优。
#include<cstdio> #include<cstring> const int LMT=50002; int sum[2][LMT],next[LMT],all,is[LMT]; struct line { int u,v,next,len; }e[LMT<<1]; void init(void) { memset(is,0,sizeof(is)); memset(sum,0,sizeof(sum)); memset(next,-1,sizeof(next)); all=0; } void insert(int u,int v,int len) { e[all].u=u; e[all].v=v; e[all].len=len; e[all].next=next[u]; next[u]=all++; } void dfs(int u,int pre) { int v,x,len,tem; for(x=next[u];x!=-1;x=e[x].next) if(e[x].v!=pre) { v=e[x].v;len=e[x].len; dfs(v,u);//优先深搜,树形DP要依据孩子的结果对父节点取值 if(is[v]) { tem=len+sum[0][u]+sum[1][v]; if(sum[1][u]+sum[0][v]+(len<<1)>tem) sum[1][u]=tem; else sum[1][u]=sum[1][u]+sum[0][v]+(len<<1); sum[0][u]+=(len<<1)+sum[0][v]; is[u]=1;//该子树有要访问的点就标记该路径 } } } int main(void) { int k,n,i,u,v,len,m; while(~scanf("%d%d",&n,&k)) { init(); for(i=1;i<n;++i) { scanf("%d%d%d",&u,&v,&len); insert(u,v,len); insert(v,u,len);//前向星 } scanf("%d",&m); for(i=1;i<=m;i++) { scanf("%d",&u); is[u]=1;//要访问的点 } dfs(k,-1); printf("%d\n",sum[1][k]); } return 0; }
POJ 1935 树形DP
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。