bzoj 2282: [Sdoi2011]消防
2024-10-19 04:26:40
#include<cstdio>
#include<cstring>
#include<iostream>
#define N 600000
using namespace std;
int cnt,n,s,head[N],next[N*],u[N*],v[N*],q[N],h,t,d[N],f[N],mx,rt1,mx1,from[N],zhan[N],tot,mark[N];
int l,r,ans;
void jia(int a1,int a2,int a3)
{
cnt++;
next[cnt]=head[a1];
head[a1]=cnt;
u[cnt]=a2;
v[cnt]=a3;
return;
}
bool pan(int a1)
{
int L=,R=tot;
for(;zhan[]-zhan[L]<=a1;L++);
for(;zhan[R]-zhan[tot]<=a1;R--);
if(zhan[L-]-zhan[R+]>s)
return ;
return ;
}
void dfs(int a1)
{
h=;
t=;
q[t]=a1;
memset(f,,sizeof(f));
f[a1]=;
d[a1]=;
for(;h<t;)
{
h++;
int p=q[h];
for(int i=head[p];i;i=next[i])
if(!f[u[i]])
{
if(mark[u[i]])
d[u[i]]=d[p];
else
d[u[i]]=d[p]+v[i];
q[++t]=u[i];
from[u[i]]=p;
f[u[i]]=;
}
}
return;
}
int main()
{
scanf("%d%d",&n,&s);
for(int i=;i<n;i++)
{
int a1,a2,a3;
scanf("%d%d%d",&a1,&a2,&a3);
jia(a1,a2,a3);
jia(a2,a1,a3);
}
dfs();
mx=;
for(int i=;i<=n;i++)
if(mx<d[i])
{
mx=d[i];
rt1=i;
}
dfs(rt1);
mx=;
for(int i=;i<=n;i++)
if(mx<d[i])
{
mx=d[i];
mx1=i;
}
r=d[mx1];
zhan[++tot]=d[mx1];
mark[mx1]=;
for(;mx1!=rt1;)
{
mx1=from[mx1];
zhan[++tot]=d[mx1];
mark[mx1]=;
}
dfs(rt1);
for(int i=;i<=n;i++)
if(d[i]>l)
l=d[i];
for(;l<=r;)
{
int mid=(l+r)>>;
if(pan(mid))
{
ans=mid;
r=mid-;
}
else
l=mid+;
}
printf("%d\n",ans);
return ;
}
显然最长距离最短,一定是在直径上,我们先DFS两遍找出直径,把直径上的边赋值成0,跑一遍dfs,找一个最大值作为l,二分答案判断。
最新文章
- WPF资源字典的使用【转】
- TOJ 2776 CD Making
- Process Explorer使用图文教程
- MyEclipse XFire Web Service
- Unity3D 常用插件
- VC2010中去掉红绝下划线
- 用css3制作旋转加载动画的几种方法
- 利用dedecms autoindex让文章列表加上序列号
- 触发器创建及Navicat中使用
- 转--Android学习笔记-实用代码合集
- Gradle用户指南(章9:Groovy快速入门)
- iOS第三方语音-讯飞语音
- iOS: 学习笔记, 透过Boolean看Swift(译自: https://developer.apple.com/swift/blog/ Aug 5, 2014 Boolean)
- linux tesseract 安装及部署tess4j项目的常见问题
- yarn安装及node升级
- python 中爬虫 content和text的区别
- cocoa开发Mac小试笔记
- OLED屏幕那些次像素有趣的排列方式
- 按时间间隔生成cron表达式
- Linux vim命令详解
热门文章
- mysql概要(六)连接
- Visual Studio 2012 RC 中RC表示什么意思
- [转载] C++ STL string的Copy-On-Write技术
- JS 字符串编码函数(解决URL特殊字符传递问题):escape()、encodeURI()、encodeURIComponent()区别详解
- mysql 查询执行的流程
- python仿微软记事本
- 使用bufferevent进行libevent服务端和客户端的开发
- Android 项目中常用到的第三方组件
- C#_加密解密
- linux笔记:网络命令ping,traceroute,ifconfig,netstat;挂载和卸载命令mount,umount