首页 > 代码库 > hiho 1050 树中的最长路 (树的直径)
hiho 1050 树中的最长路 (树的直径)
最近在复习比较简单的知识，顺便当整理代码吧。
树的直径是一个经典问题，即求树上最远两点的距离。
思路一：
任取一个点，求这个点的最远点的最远点，两遍bfs即可。
代码：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <cmath> 6 #include <algorithm> 7 #include <string> 8 #include <queue> 9 #include <stack>10 #include <vector>11 #include <map>12 #include <set>13 #include <functional>14 #include <cctype>15 #include <time.h>16 17 using namespace std;18 19 const int INF = 1<<30;20 21 struct Graph {22 static const int MAXN = (int) 1e5+55;23 static const int MAXM = MAXN*2;24 25 int head[MAXN];26 int next[MAXM], to[MAXM], use;27 28 inline void init() {29 memset(head, -1, sizeof(head));30 use = 0;31 }32 33 inline void addEdge(int u, int v) {34 next[use] = head[u];35 to[use] = v;36 head[u] = use++;37 }38 };39 40 const int MAXN = (int) 1e5+55;41 42 Graph G;43 int Que[MAXN];44 int d[MAXN];45 int n;46 47 void bfs(int st) {48 memset(d, -1, sizeof(d));49 int l = 0, r = 0;50 d[st] = 0;51 Que[r++] = st;52 while (l<r) {53 int u = Que[l++];54 for (int p = G.head[u]; p != -1; p = G.next[p]) {55 int v = G.to[p];56 if (d[v]!=-1) continue;57 d[v] = d[u] + 1;58 Que[r++] = v;59 }60 }61 }62 63 void solve() {64 bfs(1);65 bfs(Que[n-1]);66 printf("%d\n", d[Que[n-1]]);67 }68 69 int main() {70 #ifdef Phantom0171 freopen("1050.txt", "r", stdin);72 #endif //Phantom0173 74 while (scanf("%d", &n)!=EOF) {75 G.init();76 int u, v;77 for (int i = 1; i < n; i++) {78 scanf("%d%d", &u, &v);79 G.addEdge(u, v);80 G.addEdge(v, u);81 }82 solve();83 }84 85 return 0;86 }
另一种思路是树形dp，一棵树中的最长路要么在子树中，要么经过根。枚举每棵子树的最大深度和次大深度即可。
代码：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <cmath> 6 #include <algorithm> 7 #include <string> 8 #include <queue> 9 #include <stack>10 #include <vector>11 #include <map>12 #include <set>13 #include <functional>14 #include <cctype>15 #include <time.h>16 17 using namespace std;18 19 const int INF = 1<<30;20 21 struct Graph {22 static const int MAXN = (int) 1e5+55;23 static const int MAXM = MAXN*2;24 25 int head[MAXN];26 int next[MAXM], to[MAXM], use;27 28 inline void init() {29 memset(head, -1, sizeof(head));30 use = 0;31 }32 33 inline void addEdge(int u, int v) {34 next[use] = head[u];35 to[use] = v;36 head[u] = use++;37 }38 };39 40 Graph G;41 42 const int MAXN = (int) 1e5+55;43 44 int dp[MAXN];45 int ans;46 47 int dfs(int u, int pre, int cnt) {48 int fi = 0, se = 0;49 int t;50 51 for (int p = G.head[u]; p != -1; p = G.next[p]) {52 int v = G.to[p];53 if (v==pre) continue;54 t = dfs(v, u, cnt+1);55 if (t>fi) { se = fi; fi = t; }56 else if (t>se) se = t;57 }58 ans = max(ans, max(fi+cnt, fi+se));59 return fi+1;60 }61 62 int main() {63 #ifdef Phantom0164 freopen("1050.txt", "r", stdin);65 #endif //Phantom0166 67 int n, u, v;68 while (scanf("%d", &n)!=EOF) {69 G.init();70 for (int i = 1; i < n; i++) {71 scanf("%d%d", &u, &v);72 G.addEdge(u, v);73 G.addEdge(v, u);74 }75 ans = 0;76 dfs(1, 1, 0);77 printf("%d\n", ans);78 }79 80 return 0;81 }
顺便说一下，hiho上这个题的数据比较弱，开始我几个错误的代码都A了。
hiho 1050 树中的最长路 (树的直径)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。