2014 Super Training #9 E Destroy --树的直径+树形DP
2024-08-28 07:59:43
原题: ZOJ 3684 http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3684
题意: 给你一棵树,树的根是树的中心(到其他点的最远距离最小)。现在你要破坏所有叶子节点到根节点的连通,每条边破坏都需要一定能量。你有一个能量为power的武器,能破坏能量小于等于power的任何路。求最少需要的power。
解法参考博客:http://blog.csdn.net/gzh1992n/article/details/8651191,我也不是很懂,就是先找出树的中心点,然后做树形DP。
还有一种找中点的方法:
从任意点进行第一次dfs求得数的直径的一个端点,从这个端点dfs求得另一个端点,然后遍历直径,找到最接近直径一半的点就是中点。
没试过,博客http://www.cnblogs.com/hundundm/archive/2013/01/21/2870271.html里有提到。
代码:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#define ll long long
using namespace std;
#define N 10007 struct node
{
int v,len,power;
int next;
}G[*N]; const ll Mod = (ll)(1LL<<);
int head[N],tot,n;
ll dp[N];
int ma[N],sma[N]; void addedge(int u,int v,int len,int power)
{
G[tot].v = v;
G[tot].len = len;
G[tot].power = power;
G[tot].next = head[u];
head[u] = tot++;
} void dfs(int u,int fa)
{
ma[u] = ;
sma[u] = ;
for(int i=head[u];i!=-;i=G[i].next)
{
int v = G[i].v;
if(v == fa)
continue;
dfs(v,u);
int L = ma[v]+G[i].len;
if(ma[u] < L) // sma[u] < ma[u] < L
{
sma[u] = ma[u];
ma[u] = L;
}
else if(sma[u] < L) // sma[u] < L < ma[u]
sma[u] = L;
}
} void DP(int u,int fa)
{
for(int i=head[u];i!=-;i=G[i].next)
{
int v = G[i].v;
if(v == fa)
continue;
if(ma[u] == ma[v]+G[i].len) //最远的点在v的子树内
{
ma[v] = max(ma[v],sma[u]+G[i].len);
sma[v] = max(sma[v],sma[u]+G[i].len);
}
else
{
ma[v] = max(ma[v],ma[u]+G[i].len);
sma[v] = max(sma[v],ma[u]+G[i].len);
}
DP(v,u);
}
} int findCenter()
{
dfs(,);
DP(,);
int cen = min_element(ma+,ma+n+)-ma;
return cen;
} void dfs2(int u,int fa)
{
int flag = ;
ll power = ;
dp[u] = Mod;
for(int i=head[u];i!=-;i=G[i].next)
{
int v = G[i].v;
if(v == fa)
continue;
dfs2(v,u);
power = max(power,min(dp[v],(ll)G[i].power));
flag = ; //不是叶子节点
}
if(flag)
dp[u] = power;
} ll Get(int cen)
{
dfs2(cen,);
return dp[cen];
} int main()
{
int u,v,len,power;
int cen,i;
while(scanf("%d",&n)!=EOF)
{
memset(head,-,sizeof(head));
tot = ;
for(i=;i<n-;i++)
{
scanf("%d%d%d%d",&u,&v,&len,&power);
addedge(u,v,len,power);
addedge(v,u,len,power);
}
cen = findCenter();
printf("%lld\n",Get(cen));
}
return ;
}
最新文章
- TODO:字节的那点事Go篇
- 让 FreeBSD 和 Gentoo Linux 在 ZFS 存储卷上共存
- flask01 安装及初涉
- 无法在web服务器上启动调试。Microsoft Visual Studio 远程调试监视器(MSVSMON.EXE)似乎没有在远程计算机上运行,VS2012调试错误
- 第三百三十九天 how can I 坚持
- C#.Net 如何动态加载与卸载程序集(.dll或者.exe)4-----Net下的AppDomain编程 [摘录]
- Jacob
- mysql新建数据库时的collation选择(转)
- ES6中的类
- JS中有关数组Array的常用方法函数
- php实现点击文字提交表单并传递数据至下一个页面
- 01 Java jdk环境配置
- python遍历数组获取下标
- ES6 Generator的应用场景
- [leetcode] 230. Kth Smallest Element in a BST 找出二叉搜索树中的第k小的元素
- Sometimes , less is more
- ZT 80-90年代港台300部电视剧 你看过多少?
- MySQL实现强制查询走索引和强制查询不缓存
- 【linux】linux无root权限安装包的一般流程
- Vue 生产环境部署
热门文章
- 基于进程的Quartz.NET管理系统QuartzService(一)
- mysql grant all on *.* to xxx@&#39;%&#39; 报Access denied for user &#39;root&#39;@&#39;localhost&#39;
- linux线程控制&;线程分离
- Android从零开始——Android开发环境的安装
- 转:纠结的Shim
- java.lang.RuntimeException: Fail to connect to camera service问题
- Gnome排序算法
- 使用 SharedPreferences 实现数据的存储和读取
- CocoaPods的使用(图文并茂)OS X 10.11 系统
- 用Qt开发第一个Hello World程序