Find Metal Mineral

3 1 1
1 2 1
1 3 1
3 1 2
1 2 1
1 3 1

3
2

Hint
In the first case: 1->2->1->3 the cost is 3;
In the second case: 1->2; 1->3 the cost is 2;
 

题意：给定一棵树，起点，机器人个数，求遍历所有节点的最小路径和。

ddp[u][i]表示访问结束后以u为根节点的子树上机器人个数，假如有0个机器人，那么肯定是一个机器人去访问完后又返回了，因此需要特殊考虑，

代码：

/* ***********************************************
Author :xianxingwuguan
Created Time :2014-2-6 16:15:10
File Name :1.cpp
************************************************ */
#pragma comment(linker, "/STACK:102400000,102400000")
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <string>
#include <time.h>
#include <math.h>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
#define INF 1000000
#define eps 1e-8
#define pi acos(-1.0)
typedef long long ll;
const int maxn=40009;
int head[maxn],tol;
struct node{
    int next,to,val;
    node(){};
    node(int _next,int _to,int _val):next(_next),to(_to),val(_val){}
}edge[5*maxn];
void add(int u,int v,int val){
    edge[tol]=node(head[u],v,val);
    head[u]=tol++;
}
int K,dp[maxn][13];
void dfs(int u,int fa){
	for(int i=head[u];i!=-1;i=edge[i].next){
		int v=edge[i].to;
		if(v==fa)continue;
		dfs(v,u);
		for(int j=K;j>=0;j--){
			dp[u][j]+=dp[v][0]+2*edge[i].val;
			for(int k=0;k<=j;k++)
				dp[u][j]=min(dp[u][j],dp[u][j-k]+dp[v][k]+k*edge[i].val);
		}
	}
}
int main(){
	int i,j,k,m,n,s;
    while(~scanf("%d%d%d",&n,&s,&K)){
		memset(head,-1,sizeof(head));tol=0;
		for(i=1;i<n;i++){
			scanf("%d%d%d",&j,&k,&m);
			add(j,k,m);
			add(k,j,m);
		}
		memset(dp,0,sizeof(dp));
		dfs(s,-1);
		printf("%d\n",dp[s][K]);
	}
}

hdu 4003 树形dp+分组背包

原文：http://blog.csdn.net/xianxingwuguan1/article/details/18951569