题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=4003
题目大意：有K个机器人，走完树上的全部路径，每条路径有个消费。对于一个点，机器人可以出去再回来，开销2倍。也可以不回来，一直停在某个点（如果你的机器人数量足够多的话）。问最小开销。
解题思路：
其实这题只能说是类树形背包。
用dp[i][j]表示在i点，有j个不回来的机器人走过的最小开销。
比如dp[i][0]就表示，i点及其子点全部靠其它点的不回来的机器人探索。所以机器人是一来一回开销2倍。
for(K...j...0) //j可以为0
dp[i][j]+=dp[t][0]+2*e[a].w; //表示子点t全靠其它点的机器人探索
for(1..k....j) //k要从1开始了，且k最大可以为j，也就是说父亲点可以是0个机器人，子点的机器人下去之后又回到子点，又去探索新的子点的子点。这样必然有父亲点0的情况。
dp[i][j]=min(dp[i][j],dp[i][j-k]+dp[t][k]+k*e.w); //权在边的计算模板
#include "cstdio"
#include "vector"
#include "iostream"
#include "cstring"
using namespace std;
#define maxn 10005
struct Edge
{
int to,next,w;
}e[maxn*];
int dp[maxn][],head[maxn],tol;
int n,s,K,u,v,w;
void addedge(int u,int v,int w)
{
e[tol].to=v;
e[tol].next=head[u];
e[tol].w=w;
head[u]=tol++;
}
void dfs(int root,int pre)
{
int i=root;
for(int a=head[root];a!=-;a=e[a].next)
{
int t=e[a].to;
if(t==pre) continue;
dfs(t,root);
for(int j=K;j>=;j--)
{
dp[i][j]+=dp[t][]+*e[a].w;
for(int k=;k<=j;k++)
dp[i][j]=min(dp[i][j],dp[i][j-k]+dp[t][k]+k*e[a].w);
}
}
}
int main()
{
//freopen("in.txt","r",stdin);
while(~scanf("%d%d%d",&n,&s,&K))
{
memset(dp,,sizeof(dp));
memset(head,-,sizeof(head));
tol=;
for(int i=;i<n;i++)
{
scanf("%d%d%d",&u,&v,&w);
addedge(u,v,w);
addedge(v,u,w);
}
dfs(s,s);
printf("%d\n",dp[s][K]);
}
}
| 2882723 | neopenx | HDU | 4003 | Accepted | 1092 | 265 | C++ | 1072 |
2014-10-24 12:36:57
|