题目链接
题目概述
求树的直径。
题目分析
对于树的直径，《算法导论》上有这么一句：
树中所有最短路径的最大值即为树的直径。
换句话说，不重复路径的最大值即为树的直径。有以下算法可快速求出树的直径：
先对任意一个结点做 BFS / DFS 求出最远的结点，然后以这个结点为起始结点再做 BFS / DFS 到达另一个最远结点。第一次到达的结点是这个图的直径的一端，第二次到达的则为另一端。
详细证明可见此。
完整代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| #include <bits/stdc++.h>
using namespace std;
const int MAXN=10005;
int maps[MAXN][MAXN];
bool vst[MAXN][MAXN];
vector<int> dis[MAXN];
int maxlen,n,maxi;
void dfs(int x, int len){
if(maxlen<len){
maxlen=len;
maxi=x;
}
for(int i=0; i<dis[x].size(); i++){
if(vst[x][dis[x][i]]||maps[x][dis[x][i]]==0)
continue;
vst[x][dis[x][i]]=vst[dis[x][i]][x]=1;
dfs(dis[x][i], len+maps[x][dis[x][i]]);
vst[x][dis[x][i]]=vst[dis[x][i]][x]=0;
}
}
int main(){
scanf("%d", &n);
int p,q,d;
for(int i=0; i<n-1; i++){
scanf("%d%d%d", &p, &q, &d);
maps[p][q]=maps[q][p]=d;
dis[p].push_back(q);
dis[q].push_back(p);
}
dfs(1,0);
dfs(maxi,0);
int ans=0;
for(int i=1; i<=maxlen; i++)
ans+=i+10;
printf("%d\n", ans);
return 0;
}
|
自我总结
原本是以每一个结点为起点，做 DFS ，然后挑出最长路径，果断超时。然后看到有关于“树的直径”以及其快速求解的算法，才得以解决，说明还是有很多没接触过的基础性知识。以及 DFS 写起来真方便（。