题目描述
试题 算法提高 金属采集
资源限制
时间限制：1.0s 内存限制：256.0MB
问题描述
人类在火星上发现了一种新的金属！这些金属分布在一些奇怪的地方，不妨叫它节点好了。一些节点之间有道路相连，所有的节点和道路形成了一棵树。一共有 n 个节点，这些节点被编号为 1~n 。人类将 k 个机器人送上了火星，目的是采集这些金属。这些机器人都被送到了一个指定的着落点， S 号节点。每个机器人在着落之后，必须沿着道路行走。当机器人到达一个节点时，它会采集这个节点蕴藏的所有金属矿。当机器人完成自己的任务之后，可以从任意一个节点返回地球。当然，回到地球的机器人就无法再到火星去了。我们已经提前测量出了每条道路的信息，包括它的两个端点 x 和 y，以及通过这条道路需要花费的能量 w 。我们想花费尽量少的能量采集所有节点的金属，这个任务就交给你了。
输入格式
第一行包含三个整数 n, S 和 k ，分别代表节点个数、着落点编号，和机器人个数。
接下来一共 n-1 行，每行描述一条道路。一行含有三个整数 x, y 和 w ，代表在 x 号节点和 y 号节点之间有一条道路，通过需要花费 w 个单位的能量。所有道路都可以双向通行。
输出格式
输出一个整数，代表采集所有节点的金属所需要的最少能量。
所有机器人在 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 的正整数。
样例
样例输入
6 1 3
1 2 1
2 3 1
2 4 1000
2 5 1000
1 6 1000
样例输出
3004
样例说明
Tips:本题与有依赖关系的背包问题一致，转化为分组背包问题；
C++ 代码
#include<iostream>
#include<algorithm>
#include<vector>
struct kk { int go, wealth; };
std::vector<struct kk>ali[100001];
int N, S, K;
int visit[100001] = {};
int dp[100001][11] = {};
void DFS(int p)
{
visit[p] = 1;
for (int m = M; m >= 0; m--)dp[p][m] = 0;//没有子结点情况下不要继续花费能量
for (int i = 0; i < ali[p].size(); i++)
{
int son = ali[p][i].go;
if (visit[son])continue;
int cost = ali[p][i].wealth;
DFS(son);
for (int m = K; m >= 0; m--)//这里要注意不能掉了0的情况
{
dp[p][m] = dp[p][m] + (dp[son][0] + 2 * cost);
//初始情况为m个机器人全部停留在该父节点处，那么子结点就没有停留，即不管
//有多少个机器人去往子结点那么都要返回，这样一个机器人去完成这些动作是
//付出的代价是最小的；
//子树son中没有停留机器人，那么意味全反回，最少是去一个所以最少反回一个
for (int raim = 1; raim <= m; raim++)//在子树son中停raim个机器人的情况
dp[p][m] = std::min(dp[p][m], dp[p][m - raim] + raim * cost + dp[son][raim]);
}
}
}
int main(void)
{
//std::ios_base::sync_with_stdio(false);
std::cin >> N >> S >> K;//节点个数、着落点编号，和机器人个数。
struct kk tmp;
for (int i = 1; i < N; i++)
{
int a, b, c;
std::cin >> a >> b >> c;
ali[a].push_back({ b,c });
ali[b].push_back({ a,c });
}
DFS(S);
std::cout << dp[S][K];
return 0;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
