P1099 树网的核——模拟+树形结构
2024-08-29 00:03:02
P1099 树网的核
无根树,在直径上找到一条长度不超过s的路径,使得最远的点距离这条路径的距离最短;
首先两遍dfs找到直径(第二次找的时候一定要吧father[]清零)
在找到的直径下枚举长度不超过s的链,ans的下界是直径两端点到这条链距离的最小值;
然后将直径上的点都标记,再次求一下别的点到直径的距离。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=;
int n,s;
int pre[maxn],last[maxn],other[maxn],len[maxn],l; void add(int x,int y,int z)
{
l++;
pre[l]=last[x];
last[x]=l;
other[l]=y;
len[l]=z;
} int dis[maxn],father[maxn],vis[maxn];
int l1,l2; void dfs(int x)
{
for(int p=last[x];p;p=pre[p])
{
int v=other[p];
if(v==father[x]||vis[v]) continue;
father[v]=x;
dis[v]=dis[x]+len[p];
dfs(v);
}
} int main()
{
scanf("%d%d",&n,&s);
for(int i=;i<n;i++)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
add(y,x,z);
} dis[]=; dfs();
l1=;
for(int i=;i<=n;i++) if(dis[i]>dis[l1]) l1=i;
memset(father,,sizeof(father));
dis[l1]=; dfs(l1); l2=;
for(int i=;i<=n;i++) if(dis[i]>dis[l2]) l2=i; //printf("??%d %d\n",l1,l2); int ans=,j=l2;
for(int i=l2;i;i=father[i])
{
while(father[j]&&dis[i]-dis[father[j]]<=s) j=father[j];
ans=min(ans,max(dis[l2]-dis[i],dis[j]));
}
for(int i=l2;i;i=father[i]) vis[i]=;
for(int i=l2;i;i=father[i])
{
dis[i]=;
dfs(i);
}
for(int i=;i<=n;i++) ans=max(ans,dis[i]);
printf("%d",ans);
return ;
}
最新文章
- android subclipse subversive
- Ionic环境搭建
- 白话学习MVC(八)Action的执行二
- oracle11g空表不能导出记录
- unity 脚本(自定义组件)的事件触发关系
- 【转】Mybatis Generator最完整配置详解
- 学习MVC框架之一
- My Eclipse 自动提示
- CentOS 删除自带的OpenJDK 和 安装SunJDK
- Memcached初体验及原理解说
- python中循环删除列表中元素时的坑!
- MariaDB导入XXX.sql文件
- (cvpr2019 ) Better Version of SRMD
- Oracle数据库表的一些宏处理
- php使用redis的GEO地理信息类型
- freeze
- Objective-C RunTime 学习笔记 之 AutoReleasPool
- ORM表操作
- 转:Java对象序列化
- Windows10 Virtualization Technology虚拟化技术功能