题目链接:uva 1407 - Caves
题目大意:给出n,表示有一个以0为根含有n个节点的树,每条边有一个权值,现在给出m次询问,每次询问有一个val值,要求计算在val值下的距离最多能经过多少个节点,一个节点多次移动多算一次。
解题思路:dp[u][i]表示说以u为根,经过i个节点的最短距离,第三维有0和1两种状态,0是经过i个节点后要不用返回u,1是需要返回。这样就有(当考虑一个孩子节点v时):
dp[u][j][0] = min(dp[u][j][0], dp[u][j-x][1]+dp[v][x][0]+val);
dp[u][j][0] = min(dp[u][j][0], dp[u][j-x][0]+dp[v][x][1]+2*val);
dp[u][j][1] = min(dp[u][j][1], dp[u][j-x][1]+dp[v][x][1]+2*val);
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 505;
const int INF = 0x3f3f3f3f;
struct state {
int v, val;
state() { };
state(int vi, int value) {
this->v = vi;
this->val = value;
}
};
int n, m, vis[N], cnt[N], dp[N][N][2];
vector<state> g[N];
void init () {
memset(vis, 0, sizeof(vis));
memset(dp, INF, sizeof(dp));
for (int i = 0; i < n; i++) g[i].clear();
int a, b, value;
for (int i = 1; i < n; i++) {
scanf("%d%d%d", &a, &b, &value);
g[a].push_back(state(b, value));
g[b].push_back(state(a, value));
}
}
void solve (int u) {
vis[u] = cnt[u] = 1;
dp[u][1][0] = dp[u][1][1] = 0;
for (int i = 0; i < g[u].size(); i++) {
int v = g[u][i].v, val = g[u][i].val;
if (vis[v]) continue;
solve(v);
cnt[u] += cnt[v];
for (int j = cnt[u]; j > 1; j--) {
for (int x = 0; x <= j && x <= cnt[v]; x++) {
dp[u][j][0] = min(dp[u][j][0], dp[u][j-x][1]+dp[v][x][0]+val);
dp[u][j][0] = min(dp[u][j][0], dp[u][j-x][0]+dp[v][x][1]+2*val);
dp[u][j][1] = min(dp[u][j][1], dp[u][j-x][1]+dp[v][x][1]+2*val);
}
}
}
}
int main () {
int cas = 1;
while (scanf("%d", &n) == 1 && n) {
init();
solve(0);
printf("Case %d:\n", cas++);
int a;
scanf("%d", &m);
while (m--) {
scanf("%d", &a);
for (int i = n; i; i--) if (dp[0][i][0] <= a) {
printf("%d\n", i); break;
}
}
}
return 0;
}
分享到:
相关推荐
最新版,unity2019亲测可用无报错
Digger 是一个简单但功能强大的工具,可直接从 Unity 编辑器在 Unity 地形中创建自然洞穴和悬悬岩。 借助 Unity 2019.3 充分发挥 Digger 的功能!Digger 现在使用最新的 Unity 功能在地形表面上打孔,并且比以往...
Digger 是一个简单但功能强大的工具,可直接从 Unity 编辑器在 Unity 地形中创建自然洞穴和悬悬岩。 借助 Unity 2019.3 充分发挥 Digger 的功能!Digger 现在使用最新的 Unity 功能在地形表面上打孔,并且比以往任何...
Phaser Ruby入门套件 依存关系 Git(在OS X上通过自制软件安装) Ruby 2.1.2(我们建议使用RVM) 安装 ... 再次使用cd penguin-wars ,其中“ penguin-wars”是将入门工具包克隆到的目录。 bundle这将安装ruby依赖项...
Ty塔斯马尼亚虎-库姆洞(Kumu Caves)已恢复 欢迎来到库木洞! 要使用此mod,请先在此处安装ty-mod-manager: : 。 然后,将文件拖到您的Mods文件夹中,并在mod loader中激活该mod。 Undertow之家终于恢复了昔日的...
The Caves是使用Crystal Space引擎开发的3D在线角色扮演游戏。 重点将是创建一个小的(10-100)用户环境,以允许基于团队合作的任务更加集中。
建立扩充功能! Albert工具直接从问题源打开支持通知单 支持语言:English
重庆洞穴喀蛛属一新种记述(蜘蛛目:球体蛛科),窦亮,林玉成,本文记述了采自中国重庆洞穴内的球体蛛科喀蛛属一新种--心形喀蛛,并提供了详细的形态描述和鉴别特征图。模式标本保存在四川大学�
Cave cavum 是一款使用 SDL 库用 C++ 编写的街机游戏。 只需要空格键就可以玩,它\\\\\\\ 很简单,但有时会让人上瘾。 仅在 GNU/Linux 下测试(但代码不是很依赖操作系统)。
巨石洞穴纯 python 中的 Boulder Dash (tm) 克隆。 包括一个洞穴编辑器,因此您可以制作自己的游戏! 运行此程序的要求: Python 3.6 或更新版本pillow (处理图像) synthplayer (软件调频合成器) 支持的音频播放...
重制旧游戏的秘密特工。 这个想法是更好的AI(对手会奔跑,跳跃,躲闪),不同的武器等等。 计划的功能:-炮塔和陷阱-...过场动画-菜单(设置,保存,加载,选择剧集)-声音-效果更好-最后包括了Crystal Caves剧集
和声2 用户体验 QudUX 2.0 是 Qud 洞穴模组的继承者。 它已经从头开始完全重写。 现在可以在“选项”菜单中单独打开或关闭所有功能。...自动跟踪日志中访问过的位置(绿色复选标记或灰色问号) 通过外观或交互菜单在您...
标签: #sochi #russia , #journey #spring , #trip #mountain , #waterfall #nature , #photos #plants , #botany #caves , #fungi #flora , #denrarium #russia , #journey #spring , #trip #mountain ...
帆布场地(正在进行中) 使用它们作为背景的漂亮画布渲染的一些示例 查看演示-> 尚未完成 安装 npm install bower install 跑步 grunt serve 贡献 是的,请
我希望有一天将这种暴民带入香草Minecraft,因为我相信它将适合Caves&Cliffs更新目标:-使卷须朝上延伸,并将光源块作为“食物源”食用-完成-使其增长和光消耗自主-完成-使寻路使用与服务器不同的线程-完成-制作...
标签: #fauna #flora #girvas #kivach #kizi #moon #museum #oreshek #ruskeala #ruskealagapcaves #caves #karelia #russia #nature #photo #journey释放发布到: 执照Karelia-trip.CC-国际4.0评分(CC BY 4.0)...
is unable to allow terrain with overhangs and caves, and is unable to allow for destructible terrain. In this project, an alternative technique using voxels is explored to overcome these limitations ...
dst-dedicated-server:不要让带有Docker的所有平台(Linux,Mac,Windows)挨饿的专用服务器指南。 广泛的文档,包括mods的安装,服务器配置和性能,世界范围的生成以及设置管理员
本Demo是在Delphi下实现的在数据库下实现,将数据读取显示分部在饼状图上,然后另外实现Caves动画实现例子
: 和https://commons.wikimedia.org/wiki/File:Maitreya_and_disciples_carving_in_Feilai_Feng_Caves.jpg Ciro_Santilli_with_his_mother_in_law_during_the_wedding_in_2017.jpg Coitus_with_bees.jpg : ...