思维啊 dp[i][j]表示当前I节点停留了j个机器人 那么它与父亲的关系就有了 那条边就走了j遍
dp[i][j] = min(dp[i][j],dp[child][g]+dp[i][j-g]+g*w[i][child] );
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
#include<vector>
#include<cmath>
#include<queue>
using namespace std;
#define N 10010
#define LL __int64
struct node
{
int u,v,w,next;
}ed[N<<];
int head[N],t,k;
int dp[N][];
void init()
{
t = ;
memset(head,-,sizeof(head));
}
void add(int u,int v,int w)
{
ed[t].u = u;
ed[t].v = v;
ed[t].w = w;
ed[t].next = head[u];
head[u] = t++;
}
void dfs(int pre,int u)
{
int i,j;
for(i = head[u] ; i!=- ; i = ed[i].next)
{
int v = ed[i].v;
if(v==pre) continue;
dfs(u,v);
for(j = k ; j >= ; j --)
{
dp[u][j]+=dp[v][]+*ed[i].w;
for(int g = ; g <= j ; g++)
{
dp[u][j] = min(dp[u][j],dp[u][j-g]+dp[v][g]+g*ed[i].w);
}
}
}
}
int main()
{
int i,n,s;
while(scanf("%d%d%d",&n,&s,&k)!=EOF)
{
memset(dp,,sizeof(dp));
init();
for(i = ; i < n ; i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);
add(v,u,w);
}
dfs(-,s);
printf("%d\n",dp[s][k]);
}
return ;
}
hdu4003Find Metal Mineral(树形DP)的更多相关文章
-
HDU4003Find Metal Mineral[树形DP 分组背包]
Find Metal Mineral Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65768/65768 K (Java/Other ...
-
hdu 4003 Find Metal Mineral 树形DP
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4003 Humans have discovered a kind of new metal miner ...
-
HDU4003 Find Metal Mineral 树形DP
Find Metal Mineral Problem Description Humans have discovered a kind of new metal mineral on Mars wh ...
-
hdu 4003 Find Metal Mineral 树形dp ,*****
Find Metal Mineral Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65768/65768 K (Java/Other ...
-
HDU-4003 Find Metal Mineral 树形DP (好题)
题意:给出n个点的一棵树,有k个机器人,机器人从根节点rt出发,问访问完整棵树(每个点至少访问一次)的最小代价(即所有机器人路程总和),机器人可以在任何点停下. 解法:这道题还是比较明显的能看出来是树 ...
-
【树形dp】Find Metal Mineral
[HDU4003]Find Metal Mineral Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65768/65768 K (J ...
-
HDU 4003 Find Metal Mineral(分组背包+树形DP)
题目链接 很棒的一个树形DP.学的太渣了. #include <cstdio> #include <string> #include <cstring> #incl ...
-
树形DP-----HDU4003 Find Metal Mineral
Find Metal Mineral Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65768/65768 K (Java/Other ...
-
【转】【DP_树形DP专辑】【9月9最新更新】【from zeroclock&#39;s blog】
树,一种十分优美的数据结构,因为它本身就具有的递归性,所以它和子树见能相互传递很多信息,还因为它作为被限制的图在上面可进行的操作更多,所以各种用于不同地方的树都出现了,二叉树.三叉树.静态搜索树.AV ...
随机推荐
-
memcached的图形界面监控
前提是已经安装了php和memcached 图形界面的监控是通过memcache.php来实现的, 1.把该php程序拷贝到apache的web根目录 [root@cacti srv]# ...
-
HTML5 ——本地存储
目录 一.HTML4客户端存储 1.1.提交表单发送到服务器的信息 1.2.客户端本地存储概要 二.localStorage 2.1.添加 2.2.取值 2.3.修改 2.4.删除 2.5.跨页面与跨 ...
-
bzoj1758 [Wc2010]重建计划 &; bzoj2599 [IOI2011]Race
两题都是树分治. 1758这题可以二分答案avgvalue,因为avgvalue=Σv(e)/s,因此二分后只需要判断Σv(e)-s*avgvalue是否大于等于0,若大于等于0则调整二分下界,否则调 ...
-
转!!!Mybatis实现数据的增删改查(CRUD)
什么是 MyBatis? MyBatis 是支持普通 SQL 查询,存储过程和高级映射的优秀持久层框架. MyBatis 消除了几乎所有的 JDBC 代码和参数的手工设置以及对结果集的检索.MyBat ...
-
高精度计算的类(BigInteger和BigDecimal)
这两个类 在Java中没有对应的基本类型.不过,这两个类包含的方法,提供的操作与对基本类型所能执行的操作差不多. 也就是说,能对基本类型 int float 等的操作,也同样能作用于这两个类,只不过必 ...
-
iOS9新特性之UIStackView
同iOS以往每个迭代一样,iOS 9带来了很多新特性.UIKit框架每个版本都在改变,而在iOS 9比较特别的是UIStackView,它将从根本上改变开发者在iOS上创建用户界面的方式.本文将带你学 ...
-
iOS----------The Apple Developer Program License Agreement has been updated.
The Apple Developer Program License Agreement has been updated. In order to access certain membershi ...
-
2018-01-19 Xtext试用: 5步实现一个(中文)JVM语言
续上文Xtext试用: 快速实现简单领域专用语言(DSL). 基于官方教程: Five simple steps to your JVM language 达成如下语言: 它被Quan6JvmMode ...
-
swagger注释@API详细说明
swagger是当前最好用的Restful API文档生成的开源项目,通过swagger-spring项目实现了springMVC框架的无缝集成功能,方便生成restful风格的接口文档, 同时,s ...
-
chrome浏览器插件 Octotree 让你浏览GitHub的时候像IDE 一样提供项目目录
GitHub 作为代码托管平台,竟然没有提供项目目录,方便用户在线快速浏览项目结构.所以,在线分析项目源码就会变得很繁琐,必须一层一层点击,然后再一次一次地向上返回.要知道,本来 GitHub 网站在 ...