首页 > 代码库 > HDU 5758 Explorer Bo（树形DP）
HDU 5758 Explorer Bo（树形DP）
【题目链接】 http://acm.hdu.edu.cn/showproblem.php?pid=5758
【题目大意】
给出一棵树，每条路长度为1，允许从一个节点传送到任意一个节点，现在要求在传送次数尽量少的情况下至少经过每条路一遍啊，同时最小化走过的路程总长度。输出路程总长度。
【题解】
首先，对于传送次数尽量少这个条件，我们很容易发现，当且仅当每次出发点和终止点都是叶节点的时候，是最少的，当然在叶节点无法两两匹配的时候，再多走一条链。
然后就是叶节点的匹配问题，使得匹配后的叶节点连线覆盖全图的路径并且经过的总长度最短，这时候考虑考虑每条边对答案的贡献情况，由于匹配方案不唯一，因此每条边的贡献是利用dp使得耗费最小化的。
考虑到边每条边最多经过两次，至少经过一次，那么我们枚举这条边两边的情况，在这个点匹配完一些叶节点后还剩下一些链是没有被匹配的时候所能够做到的最小花费。dp[x][i][j]表示，x节点，在当前的遍历情况下，有i个叶节点没有匹配，j条单独链作为最后多走的一条链的最小花费，显然i最多不超过2，j最多不超过1。那么做一个树形DP，将各种情况从子节点转移到根节点即可，由于考虑到图形的特殊性，一开始树的遍历起点不能是叶节点，才能保证每种情况的遍历。
【代码】
#pragma comment(linker, "/STACK:1024000000,1024000000") #include <cstdio>#include <vector>#include <algorithm> #include <cstring>using namespace std;const int N=200005;int T,n,k,s[5][2],x,y,dp[N][5][2];long long ans;vector<int> g[N];void dfs(int x,int pre){ if(g[x].size()==1)dp[x][0][1]=dp[x][1][0]=0; else dp[x][0][0]=0; for(int i=0;i<g[x].size();i++){ int p=g[x][i]; if(p==pre)continue; dfs(p,x); memset(s,60,sizeof(s)); for(int j=2;j>=0;j--)for(int k=2;k;k--) for(int U=0;U<=min(j,k);U++){ int t=j+k-2*U; s[t][0]=min(s[t][0],dp[x][j][0]+dp[p][k][0]+k); s[t][1]=min(s[t][1],dp[x][j][0]+dp[p][k][1]+k); s[t][1]=min(s[t][1],dp[x][j][1]+dp[p][k][0]+k); }memcpy(dp[x],s,sizeof(dp[x])); }for(int i=2;i;i--)dp[x][i-1][1]=min(dp[x][i-1][1],dp[x][i][0]);}int main(){ scanf("%d",&T); while(T--){ scanf("%d",&n); for(int i=1;i<=n;i++)g[i].clear(); for(int i=1;i<n;i++){ scanf("%d%d",&x,&y); g[x].push_back(y);g[y].push_back(x); }if(n<=2)printf("%d\n",n-1); else{ memset(dp,60,sizeof(dp)); for(int i=1;i<=n;i++)if(g[i].size()>1){ dfs(i,-1); printf("%d\n",min(dp[i][0][0],dp[i][0][1])); break; } } }return 0;}
HDU 5758 Explorer Bo（树形DP）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。