hdu 4003 Find Metal Mineral 树形DP
2024-08-27 20:13:42
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4003
Humans have discovered a kind of new metal mineral on Mars which are distributed in point‐like with paths connecting each of them which formed a tree. Now Humans launches k robots on Mars to collect them, and due to the unknown reasons, the landing site S of all robots is identified in advanced, in other word, all robot should start their job at point S. Each robot can return to Earth anywhere, and of course they cannot go back to Mars. We have research the information of all paths on Mars, including its two endpoints x, y and energy cost w. To reduce the total energy cost, we should make a optimal plan which cost minimal energy cost.
题意描述:火星上有很多矿山(n<=10000),人们发射k(k<=10)个机器人着陆在火星上的S矿山上,目的就是采取每座矿山上的资源。一些矿山之间相互连接着,从一个矿山到另一个与其相连的矿山要消耗能量,问其最少的消耗能量是多少。
算法分析:树形DP,dp[u][i]定义为以u为根的子树中分配了i个机器人消耗的最少能量,特别的是,dp[u][0]表示为以u为树根的子树中分配了一个机器人并且机器人要在走完这颗子树后要回到u点(就相当于没有给子树分配)的最少消耗能量。
那么我们可以列出式子:dp[u][i]=min(dp[u][i],dp[u][i-j]+dp[v][j]+j*cost)(v为u的相邻节点,w为这条路的能量消耗)。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<vector>
#include<map>
#define inf 0x7fffffff
using namespace std;
const int maxn=+; int n,s,k;
int father[maxn],dp[maxn][];
vector<pair<int,int> > G[maxn]; void dfs(int u,int f)
{
father[u]=f;
int num=G[u].size();
for (int i= ;i<num ;i++)
{
int v=G[u][i].first;
int cost=G[u][i].second;
if (v==f) continue;
dfs(v,u);
for (int j=k ;j>= ;j--)
{
dp[u][j] += dp[v][]+*cost;
for (int q= ;q<=j ;q++)
dp[u][j]=min(dp[u][j],dp[u][j-q]+dp[v][q]+q*cost);
}
}
} int main()
{
while (scanf("%d%d%d",&n,&s,&k)!=EOF)
{
memset(father,-,sizeof(father));
memset(dp,,sizeof(dp));
for (int i= ;i<=n ;i++) G[i].clear();
int a,b,c;
for (int i= ;i<n- ;i++)
{
scanf("%d%d%d",&a,&b,&c);
G[a].push_back(make_pair(b,c));
G[b].push_back(make_pair(a,c));
}
dfs(s,-);
printf("%d\n",dp[s][k]);
}
return ;
}
最新文章
- Git异常:Cannot delete the branch &#39;test1&#39; which you are currently on
- laravel 框架使用总结 limit
- C和指针 第十二章 结构体 整体赋值 error: expected expression
- 译\Node.js应用的持续部署
- Tab切换
- PDO事务处理
- jquery 中的 return false 不起作用
- 一次关于使用status作为变量引发的bug及思考
- HDU 5128 The E-pang Palace(2014广州赛区现场赛B题 计算几何)
- android: startActivityForResult用法详解
- nc 反弹链接
- IDE硬盘 SCSI硬盘 SATA硬盘
- wordpress网站被挂马以及防御方法
- CountDownLatch使用例子
- type和role属性有什么区别呢
- extern “C”调用测试与验证-2016.01.06
- ☀【Zepto】touch events
- Mysql 存储过程和函数区别
- Tree 使用方式
- Linux下安装oracle11g