【tyvj1520】 树的直径
2018-06-17 21:55:02来源:未知 阅读 ()
描述 Description
树的直径,即这棵树中距离最远的两个结点的距离。每两个相邻的结点的距离为1,即父亲结点与儿子结点或儿子结点与父子结点之间的距离为1.有趣的是,从树的任意一个结点a出发,走到距离最远的结点b,再从结点b出发,能够走的最远距离,就是树的直径。树中相邻两个结点的距离为1。你的任务是:给定一棵树,求这棵树中距离最远的两个结点的距离。
输入格式 InputFormat
输入共n行
第一行是一个正整数n,表示这棵树的结点数
接下来的n-1行,每行三个正整数a,b,w。表示结点a和结点b之间有一条边,长度为w
数据保证一定是一棵树,不必判错。
输出格式 OutputFormat
输出共一行
第一行仅一个数,表示这棵树的最远距离
样例输入 SampleInput
4 1 2 10 1 3 12 1 4 15
样例输出 SampleOutput
27
数据范围和注释 Hint
10%的数据满足1<=n<=5
40%的数据满足1<=n<=100
100%的数据满足1<=n<=10000 1<=a,b<=n 1<=w<=10000
题解
1 #include<cstdio> 2 #include<iostream> 3 #include<algorithm> 4 #include<cstring> 5 #include<vector> 6 #define ll long long 7 using namespace std; 8 ll read(){ 9 int x=0,f=1;char ch=getchar(); 10 while(ch<'0'||ch>'9'){ if(ch=='-')f=-1;ch=getchar();} 11 while(ch>='0'&&ch<='9'){ x=x*10+ch-'0';ch=getchar();} 12 return x*f; 13 } 14 int X,n,q[100005],d[100005]; 15 vector<int> e[100005],len[100005]; 16 char ch[5]; 17 void bfs(int x){ 18 X=0; 19 int head=0,tail=1; 20 q[0]=x; 21 memset(d,0,sizeof(d)); 22 while(head!=tail){ 23 int now=q[head];head++; 24 if(d[now]>d[X]) X=now; 25 for(int i=0;i<e[now].size();i++){ 26 if(!d[e[now][i]]&&e[now][i]!=x){ 27 d[e[now][i]]=d[now]+len[now][i]; 28 q[tail++]=e[now][i]; 29 } 30 } 31 } 32 } 33 int main(){ 34 n=read(); 35 for(int i=1;i<n;i++){ 36 int u=read(),v=read(),w=read(); 37 e[u].push_back(v); len[u].push_back(w); 38 e[v].push_back(u); len[v].push_back(w); 39 } 40 bfs(1); bfs(X); 41 printf("%d\n",d[X]); 42 return 0; 43 }
DP
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<algorithm> 5 #define maxn 10005 6 #define inf 0x7fffffff 7 using namespace std; 8 int n,cnt,ans; 9 int f1[maxn],f2[maxn],last[maxn]; //f1求最长链,f2求次长链 10 struct edge{ 11 int to,next,v; 12 }e[maxn<<1]; 13 void add(int u,int v,int w){ 14 e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;e[cnt].v=w; 15 } 16 void dp(int x,int fa){ 17 for(int i=last[x];i;i=e[i].next){ 18 int y=e[i].to; 19 if(y==fa) continue; 20 dp(y,x); 21 if(f1[y]+e[i].v>f1[x]){ 22 f2[x]=f1[x]; 23 f1[x]=f1[y]+e[i].v; 24 } 25 else f2[x]=max(f2[x],f1[y]+e[i].v); 26 } 27 ans=max(f1[x]+f2[x],ans); 28 } 29 int main(){ 30 ios::sync_with_stdio(false); 31 cin>>n; 32 for(int i=1;i<n;i++){ 33 int u,v,w; 34 cin>>u>>v>>w; 35 add(u,v,w); add(v,u,w); 36 } 37 dp(1,0); 38 cout<<ans<<endl; 39 return 0; 40 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:C++学习的小Tips
下一篇:UVW源码漫谈(二)
- P1358 扑克牌 2020-05-06
- 表达式·表达式树·表达式求值 2020-04-29
- C++ 函数模板 2020-04-24
- 螺旋矩阵问题 2020-04-18
- [题记-并查集] 合根植物 - 蓝桥杯 2020-04-07
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash