hdu 4276 树形m时间1进n出
2024-10-19 13:18:14
http://acm.hdu.edu.cn/showproblem.php?pid=4276
一般题目是求回到原地,而这道题规定从1进n出。所以1-n这条路是必走,其他走不走无所谓。
这样很自然通过dfs先处理1-n这条路,统计这条路的花费时间cost,同时将这条上的边权设为0。
接下来就是求m-cost时间遍历能产生的最大价值,也就是最普通的问题。在这里因为1-n这条路边权已经为0,所以一定会走,只要m-cost时间能回到1点就行。
所以我觉得将1-n边权置为0是这道题的点睛之笔。
#include <iostream>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <cctype>
#include <vector>
#include <iterator>
#include <set>
#include <map>
#include <sstream>
using namespace std; #define mem(a,b) memset(a,b,sizeof(a))
#define pf printf
#define sf scanf
#define spf sprintf
#define pb push_back
#define debug printf("!\n")
#define MAXN 1000+5
#define MAX(a,b) a>b?a:b
#define blank pf("\n")
#define LL long long
#define ALL(x) x.begin(),x.end()
#define INS(x) inserter(x,x.begin())
#define pqueue priority_queue
#define INF 0x3f3f3f3f int n,m; struct node{int y,val,next;}tree[MAXN<<]; int head[MAXN],vis[MAXN],ptr=,dp[MAXN][MAXN],a[MAXN],vis2[MAXN]; void init()
{
mem(head,-);
mem(vis,);
mem(vis2,);
mem(dp,);
ptr=;
}
void add(int x,int y,int val)
{
tree[ptr].y = y;
tree[ptr].val = val;
tree[ptr].next = head[x];
head[x] = ptr++;
} int cost; void dfs(int rt)
{
vis[rt]=;
for(int i = ;i<=m;i++) dp[rt][i] = a[rt];
for(int i = head[rt];i!=-;i=tree[i].next)
{
int y = tree[i].y;
if(vis[y]) continue;
dfs(y);
for(int j=m;j>=;j--)
{
for(int k=;k<=j;k++)
{
if(j-k-*tree[i].val>=)
dp[rt][j] = max(dp[rt][j],dp[rt][j-k-*tree[i].val]+dp[y][k]);
}
}
}
} bool dfs2(int rt)
{
vis2[rt] = ;
for(int i = head[rt];i!=-;i=tree[i].next)
{
int y = tree[i].y;
if(vis2[y]) continue;
if(y==n)
{
cost+=tree[i].val;
return true;
}
if(dfs2(y))
{
cost+=tree[i].val;
tree[i].val = ;
return true;
}
}
} int main()
{
int i,j,k,t;
while(~sf("%d%d",&n,&m))
{
init();
cost = ;
for(i=;i<n;i++)
{
int x,y,z;
sf("%d%d%d",&x,&y,&z);
add(x,y,z);
add(y,x,z);
}
for(i=;i<=n;i++) sf("%d",&a[i]);
dfs2();
if(cost>m)
{
pf("Human beings die in pursuit of wealth, and birds die in pursuit of food!\n");
continue;
}
m-=cost;
dfs();
pf("%d\n",dp[][m]);
}
}
最新文章
- iOS代码汉字转拼音
- JDBC查询指定条件的数据
- sharepoint列表如何进行随机取几条记录?
- UVA1555-- Garland(推导+二分)
- 暑假热身 D. 条形码设计
- 注册表操作命令和自定义cmd窗口
- Inno Setup入门(十一)——完成安装后执行某些程序
- 剑指 offer set 8 树的子结构
- 【JPA】query新对象 需要 构造函数
- 利用socket模块检查端口存活并邮件警报
- IT行业能力细分
- 分享一款简单好用的HTML拼接工具
- 删除链表中倒数第n个节点
- 不可思议的混合模式 background-blend-mode
- Arduino抢答器
- Oracle中时间和日期函数总结
- 微信小程序 画布drawImage实现图片截取
- Gephi 网络图可视化工具
- 复习C++:VS2008中的宏干嘛用的
- Oracle varchar与varchar2的区别
热门文章
- pychram编写代码鼠标变粗处理
- Nodejs 文档概览
- loj#6435. 「PKUSC2018」星际穿越(倍增)
- 关于如何在Windows下测交互题
- Luogu1829 JZPTAB
- kuangbin专题十六 KMP&;&;扩展KMP HDU1686 Oulipo
- Appium教程——Desired Capabilities 详解(转自TesterHome)
- Java类成员变量、普通成员变量、初始化块、构造方法的初始化和执行顺序
- Django之ORM其他骚操作 执行原生SQl
- P2896 [USACO08FEB]一起吃饭Eating Together