算法提高 金属采集

Posted on | In |

问题描述

人类在火星上发现了一种新的金属！这些金属分布在一些奇怪的地方，不妨叫它节点好了。一些节点之间有道路相连，所有的节点和道路形成了一棵树。一共有 n 个节点，这些节点被编号为 1~n 。人类将 k 个机器人送上了火星，目的是采集这些金属。这些机器人都被送到了一个指定的着落点， S 号节点。每个机器人在着落之后，必须沿着道路行走。当机器人到达一个节点时，它会采集这个节点蕴藏的所有金属矿。当机器人完成自己的任务之后，可以从任意一个节点返回地球。当然，回到地球的机器人就无法再到火星去了。我们已经提前测量出了每条道路的信息，包括它的两个端点 x 和 y，以及通过这条道路需要花费的能量 w 。我们想花费尽量少的能量采集所有节点的金属，这个任务就交给你了。

输入格式
第一行包含三个整数 n, S 和 k ，分别代表节点个数、着落点编号，和机器人个数。

接下来一共 n-1 行，每行描述一条道路。一行含有三个整数 x, y 和 w ，代表在 x 号节点和 y 号节点之间有一条道路，通过需要花费 w 个单位的能量。所有道路都可以双向通行。

输出格式
输出一个整数，代表采集所有节点的金属所需要的最少能量。
样例输入
6 1 3
1 2 1
2 3 1
2 4 1000
2 5 1000
1 6 1000
样例输出
3004
样例说明
所有机器人在 1 号节点着陆。

第一个机器人的行走路径为 1->6 ，在 6 号节点返回地球，花费能量为1000。

第二个机器人的行走路径为 1->2->3->2->4 ，在 4 号节点返回地球，花费能量为1003。

第一个机器人的行走路径为 1->2->5 ，在 5 号节点返回地球，花费能量为1001。

数据规模与约定
本题有10个测试点。

对于测试点 1~2 ， n <= 10 ， k <= 5 。

对于测试点 3 ， n <= 100000 ， k = 1 。

对于测试点 4 ， n <= 1000 ， k = 2 。

对于测试点 5~6 ， n <= 1000 ， k <= 10 。

对于测试点 7~10 ， n <= 100000 ， k <= 10 。

道路的能量 w 均为不超过 1000 的正整数。

算法：

树形DP

定义dp（i，j）为从i出发，使用j个机器人的最小值

i的子树为son


dp(i,j)=(dp(son,0)+cast[son]2)(子树没有停留机器人)+min(dp[p][m-remain]+remaincost[son]+dp[son][remain])(子树停留了remain个机器人)

树状数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<iostream>
#include<cstring>
#include<cmath>
#include<vector>
#define MAX 100002
using namespace std;
int n,s,K;
struct node{
	int v;
	int w;
	node(int vv,int ww):v(vv),w(ww){
		
	}
	node(){
		
	}
};
vector<node> g[MAX];
int dp[MAX][11];
int vis[MAX];
//dp[m][n] 表示以m节点为根 停留n个机器人 的最小花费（可以再其子树上） 
using namespace std;
void dfs(int u){
	vis[u]=1;
	for(int i=0;i<g[u].size();i++){
		int v=g[u][i].v;
		int cost=g[u][i].w;
		if(vis[v]) continue;
		dfs(v);
		for(int k=K;k>=0;k--){//这里要注意不能掉了0的情况
			dp[u][k]+=dp[v][0]+cost*2;
			for(int r=1;r<=k;r++){
				dp[u][k]=min(dp[u][k],dp[u][k-r]+dp[v][r]+cost*r);
			}
		}
	}
	
	
}
int main(){
//	freopen("57.txt","r",stdin);
	cin>>n>>s>>K;
	memset(vis,0,sizeof(vis));
	memset(dp,0,sizeof(dp));
	for(int i=0;i<n-1;i++){
		int a,b,c;
		cin>>a>>b>>c;
		g[a].push_back(node(b,c));
		g[b].push_back(node(a,c));
	} 
	dfs(s);
	cout<<dp[s][K]<<endl;
}

参考链接
https://blog.csdn.net/wximo/article/details/27318767
http://www.voidcn.com/article/p-omlkxdkv-qn.html