首页 > 代码库 > 【模板】tyvjP1520 树的直径 [2017年5月计划 清北学堂Day3]
【模板】tyvjP1520 树的直径 [2017年5月计划 清北学堂Day3]
P1520 树的直径
时间: 1000ms / 空间: 131072KiB / Java类名: Main
描述
树的直径，即这棵树中距离最远的两个结点的距离。每两个相邻的结点的距离为1，即父亲结点与儿子结点或儿子结点与父子结点之间的距离为1.有趣的是，从树 的任意一个结点a出发，走到距离最远的结点b，再从结点b出发，能够走的最远距离，就是树的直径。树中相邻两个结点的距离为1。你的任务是：给定一棵树， 求这棵树中距离最远的两个结点的距离。
输入格式
输入共n行
第一行是一个正整数n，表示这棵树的结点数
接下来的n-1行，每行三个正整数a,b,w。表示结点a和结点b之间有一条边，长度为w
数据保证一定是一棵树，不必判错。
第一行是一个正整数n，表示这棵树的结点数
接下来的n-1行，每行三个正整数a,b,w。表示结点a和结点b之间有一条边，长度为w
数据保证一定是一棵树，不必判错。
输出格式
输出共一行
第一行仅一个数，表示这棵树的最远距离
第一行仅一个数，表示这棵树的最远距离
测试样例1
输入
4
1 2 10
1 3 12
1 4 15
输出
27
备注
10%的数据满足1<=n<=5
40%的数据满足1<=n<=100
100%的数据满足1<=n<=10000 1<=a,b<=n 1<=w<=10000Tgotmacp
40%的数据满足1<=n<=100
100%的数据满足1<=n<=10000 1<=a,b<=n 1<=w<=10000Tgotmacp
两种方法。
第一种，钦定一个根节点，以香港记者的速度跑一边BFS并找到最长链。
然后钦定最长链的终点为根，再以香港记者的速度跑一边BFS，找到的最长链就是直径。
第二种，钦定一个根节点，dfs或dfs，从下往上，记dp1[i]为节点i下面子树的最长链长，dp2[i]为节点i下面子树的次长链长，答案是两个加和。
求-1s
方法1：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cstring> 5 #include <algorithm> 6 #define max(a,b) ((a) > (b) ? (a) : (b)) 7 #define min(a,b) ((a) > (b) ? (b) : (a)) 8 #define lowbit(a) ((a) & (-(a))) 9 10 int read()11 {12 int x = 0;char ch = getchar();char c = ch;13 while(ch > ‘9‘ || ch < ‘0‘)c = ch, ch = getchar();14 while(ch <= ‘9‘ && ch >= ‘0‘)x = x * 10 + ch - ‘0‘, ch = getchar();15 if(c == ‘-‘)return -x;16 return x;17 }18 19 const int INF = 0x3f3f3f3f;20 const int MAXN = 10000 + 10;21 const int MAXE = MAXN * 2;22 23 int head[MAXN];24 int cnt;25 int n;26 int tmp1,tmp2,tmp3;27 struct Edge28 {29 int u,v,w,next;30 }edge[MAXE];31 inline void insert(int a,int b,int c)32 {33 edge[++cnt] = Edge{a,b,c,head[a]};34 head[a] = cnt;35 }36 inline void init()37 {38 n = read();39 for(int i = 1;i < n;i ++)40 {41 tmp1 = read();tmp2 = read();tmp3 = read();42 insert(tmp1, tmp2, tmp3);43 insert(tmp2, tmp1, tmp3);44 } 45 }46 47 int queue[MAXN];48 int ans;49 bool b[MAXN];50 int lenth[MAXN];//lenth[i]表示节点i到根节点的长度 51 int bfs(int root)52 {53 memset(queue, 0, sizeof(queue));54 memset(b, 0, sizeof(b));55 int head = 1,tail = 1;56 int a = 1;57 queue[tail] = root;58 lenth[root] = 0;59 b[root] = true;60 61 int mnode = root,m = 0;62 do63 {64 int x = queue[head];65 head ++;66 for(int pos = ::head[x];pos;pos = edge[pos].next)67 {68 int tmp = edge[pos].v;69 if(!b[tmp])70 {71 b[tmp] = true;72 queue[++tail] = tmp;73 lenth[tmp] = lenth[x] + edge[pos].w;74 if(lenth[tmp] > m)m = lenth[tmp],mnode = tmp;75 a ++;76 }77 }78 }while(a < n); 79 ans = max(ans, m);80 return mnode;81 }82 inline void work()83 {84 bfs(bfs(1));85 }86 inline void shuchu()87 {88 printf("%d", ans);89 }90 int main()91 {92 init();93 work();94 shuchu();95 return 0;96 }
方法2：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cstring> 5 #include <algorithm> 6 #define max(a,b) ((a) > (b) ? (a) : (b)) 7 #define min(a,b) ((a) > (b) ? (b) : (a)) 8 #define lowbit(a) ((a) & (-(a))) 9 10 int read() 11 { 12 int x = 0;char ch = getchar();char c = ch; 13 while(ch > ‘9‘ || ch < ‘0‘)c = ch, ch = getchar(); 14 while(ch <= ‘9‘ && ch >= ‘0‘)x = x * 10 + ch - ‘0‘, ch = getchar(); 15 if(c == ‘-‘)return -x; 16 return x; 17 } 18 19 const int INF = 0x3f3f3f3f; 20 const int MAXN = 10000 + 10; 21 const int MAXE = MAXN * 2; 22 23 int head[MAXN]; 24 int cnt; 25 int n; 26 int tmp1,tmp2,tmp3; 27 struct Edge 28 { 29 int u,v,w,next; 30 }edge[MAXE]; 31 inline void insert(int a,int b,int c) 32 { 33 edge[++cnt] = Edge{a,b,c,head[a]}; 34 head[a] = cnt; 35 } 36 inline void init() 37 { 38 n = read(); 39 for(int i = 1;i < n;i ++) 40 { 41 tmp1 = read();tmp2 = read();tmp3 = read(); 42 insert(tmp1, tmp2, tmp3); 43 insert(tmp2, tmp1, tmp3); 44 } 45 } 46 47 int queue[MAXN]; 48 int ans; 49 bool b[MAXN]; 50 int dp1[MAXN];//最长路 51 int dp2[MAXN];//次长路 52 int lenth[MAXN];//lenth[i]表示节点i到根节点的长度 53 void bfs(int root) 54 { 55 int head = 1,tail = 1; 56 int a = 1; 57 queue[tail] = root; 58 lenth[root] = 0; 59 b[root] = true; 60 61 int mnode = root,m = 0; 62 do 63 { 64 int x = queue[head]; 65 head ++; 66 for(int pos = ::head[x];pos;pos = edge[pos].next) 67 { 68 int tmp = edge[pos].v; 69 if(!b[tmp]) 70 { 71 b[tmp] = true; 72 queue[++tail] = tmp; 73 a ++; 74 } 75 } 76 }while(a < n); 77 for(int i = tail;i >= 1;i --) 78 { 79 int x = queue[i]; 80 if(!::head[i]) 81 { 82 b[i] = false; 83 } 84 else 85 { 86 int m1 = 0,m2 = 0; 87 for(int pos = ::head[x];pos;pos = edge[pos].next) 88 { 89 int tmp = edge[pos].v; 90 if(!b[tmp]) 91 { 92 if(m1 < dp1[tmp] + edge[pos].w) 93 { 94 m2 = m1; 95 m1 = dp1[tmp] + edge[pos].w; 96 } 97 else if(m2 < dp1[tmp] + edge[pos].w) 98 { 99 m2 = dp1[tmp] + edge[pos].w;100 }101 }102 }103 dp1[x] = m1;dp2[x] = m2;104 }105 b[x] = false;106 ans = max(ans, dp1[x] + dp2[x]);107 }108 }109 inline void work()110 {111 bfs(1);112 }113 inline void shuchu()114 {115 printf("%d", ans);116 }117 int main()118 {119 init();120 work();121 shuchu();122 return 0;123 }
【模板】tyvjP1520 树的直径 [2017年5月计划 清北学堂Day3]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。