【BZOJ1509】[NOI2003]逃学的小孩 直径
直径
2023-09-11 14:15:24 时间
【BZOJ1509】[NOI2003]逃学的小孩
Description
![](http://www.lydsy.com/JudgeOnline/images/1509.jpg)
Input
第一行是两个整数N(3 N 200000)和M,分别表示居住点总数和街道总数。以下M行,每行给出一条街道的信息。第i+1行包含整数Ui、Vi、Ti(1Ui, Vi N,1 Ti 1000000000),表示街道i连接居住点Ui和Vi,并且经过街道i需花费Ti分钟。街道信息不会重复给出。
Output
仅包含整数T,即最坏情况下Chris的父母需要花费T分钟才能找到Chris。
Sample Input
4 3
1 2 1
2 3 1
3 4 1
1 2 1
2 3 1
3 4 1
Sample Output
4
题解:显然A和B是直径的两端点吧~(自己瞎证一下,或者瞎yy一下就行)
然后枚举C就做完了。
#include <cstdio> #include <cstring> #include <iostream> using namespace std; const int maxn=200010; typedef long long ll; int n,cnt,r1,r2,rt; ll ans; int to[maxn<<1],next[maxn<<1],head[maxn]; ll val[maxn<<1],dep[maxn<<1],f[maxn<<1]; inline int rd() { int ret=0,f=1; char gc=getchar(); while(gc<'0'||gc>'9') {if(gc=='-') f=-f; gc=getchar();} while(gc>='0'&&gc<='9') ret=ret*10+gc-'0',gc=getchar(); return ret*f; } inline void add(int a,int b,int c) { to[cnt]=b,val[cnt]=c,next[cnt]=head[a],head[a]=cnt++; } void dfs(int x,int fa) { if(dep[x]>dep[rt]) rt=x; for(int i=head[x];i!=-1;i=next[i]) if(to[i]!=fa) dep[to[i]]=dep[x]+val[i],dfs(to[i],x); } int main() { n=rd(),rd(); int i,a,b,c; memset(head,-1,sizeof(head)); for(i=1;i<n;i++) a=rd(),b=rd(),c=rd(),add(a,b,c),add(b,a,c); dfs(1,0),r1=rt; dep[r1]=0,dfs(r1,0),r2=rt,memcpy(f,dep,sizeof(dep)); dep[r2]=0,dfs(r2,0); for(i=1;i<=n;i++) ans=max(ans,dep[r1]+min(dep[i],f[i])); printf("%lld",ans); return 0; }
相关文章
- AutoCAD如何又快又好标注直径
- Java实现 LeetCode 543. 二叉树的直径(遍历树)
- Java实现 LeetCode 543. 二叉树的直径(遍历树)
- Java实现 LeetCode 543. 二叉树的直径(遍历树)
- Java实现 LeetCode 543 二叉树的直径
- Java实现 LeetCode 543 二叉树的直径
- Java实现 LeetCode 543 二叉树的直径
- 【二叉树】LeetCode 543. 二叉树的直径【简单】
- 【二叉树】LeetCode 543. 二叉树的直径【简单】
- 大臣的旅费(树的直径)
- ( “树” 之 DFS) 543. 二叉树的直径 ——【Leetcode每日一题】
- 【LeetCode 简单 树 python3】543. 二叉树的直径
- [LeetCode] 543. 二叉树的直径 ☆(递归、数最大深度)
- zoj 3820 Building Fire Stations (二分+树的直径)
- hdu4607Park Visit 树的直径
- 刷题记录:牛客NC52867Highway [求树的直径]
- 【LeetCode】543. 二叉树的直径