1eHz

用户名：dxy1397

访问量：16243

签　名：

等　　级
排　　名	1114
经　　验	3194
参赛次数	0
文章发表	15
年　　龄	0
在职情况	学生
学　　校	武汉
专　　业

　　自我简介：

TA的其他文章

蓝桥杯基础练习VIP-报时助手-题解（C++代码）思路清晰
浏览：250

蓝桥杯历届试题-九宫重排-题解（C++代码）双向BFS满分题解
浏览：406

蓝桥杯2014年第五届真题-兰顿蚂蚁-题解（C++代码）只要19行？
浏览：370

你可能喜欢

✔✔✔ 树的直径问题+DFS求解 [c++]

　　作者: 1eHz　　　　发表时间：2021-03-23 19:01:56 浏览：912　|　评论：0　

原题链接：蓝桥杯2013年第四届真题-大臣的旅费

典型的**树的直径**问题：图中所有最短路径的最大值即为「直径」，可以用两次 DFS 或者树形 DP 的方法在 O(n) 时间求出树的直径。
题解以两遍DFS为例
**定理：**在一个连通无向无环图中，以任意结点出发所能到达的最远结点，一定是该图直径的端点之一。
*↑证明比较复杂，记住就可以了*

------------

DFS第一遍：从图中任意一点x开始，得到距离x最远的一点y；
DFS第二遍：从点y开始，得到距离点y最远的一点z；
即：点y、z是树的直径的两个端点，根据y、z两点距离可以算出题意答案。

```cpp
#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 10001;
vector< pair<int,int> >edge[MAXN];  //用STL构造的邻接表
int node, length = 0, vis[MAXN] = {0};  // 第二遍DFS起点node，与点node的距离，标记数组
void dfs(int cur, int tal){  //朴实无华的DFS
	if(tal > length){
		node = cur;
		length = tal;
	}
	int lim = edge[cur].size();
	for(int i=0;i<lim;i++){
		int suc = edge[cur].at(i).first;
		if(vis[suc]) continue;
		vis[suc] = 1;
		dfs(suc, tal+edge[cur].at(i).second);
		vis[suc] = 0;
	}
}

int main(){
	int n,p,q,d;
	cin>>n;
	for(int i=1; i<n; i++){
		cin>>p>>q>>d;
		edge[p].push_back(make_pair(q,d));
		edge[q].push_back(make_pair(p,d));
	}
	vis[1] = 1;  //标记第一遍DFS的起点1（任意起点）
	dfs(1,0);
	vis[1] = 0;
	length = 0;
	vis[node] = 1;  //标记第二遍DFS的起点node
	dfs(node, 0);
	cout<<(length*10)+((length+1)*length/2)<<endl;  //根据距离计算费用并输出
	return 0;
}
```

0.0分

20 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

1eHz

TA的其他文章

你可能喜欢

明明的随机数（C++代码）

图形输出（Java代码）

C语言训练-素数问题（C语言代码）

C二级辅导-同因查找（C语言代码）

C语言训练-求函数值（C语言代码）

✔✔✔ 树的直径问题+DFS求解 [c++]

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C二级辅导-公约公倍（C语言代码）

打水问题（C语言代码）

C语言程序设计教程（第三版）课后习题6.2 （C语言代码）

C语言程序设计教程（第三版）课后习题5.6 （C语言代码）

蓝桥杯历届试题-翻硬币（C++代码）

C语言程序设计教程（第三版）课后习题11.5 （C语言代码）

Tom数（C语言代码）

C二级辅导-等差数列（C语言代码）

C语言训练-自守数问题（C语言代码）

1eHz

TA的其他文章

你可能喜欢

明明的随机数 （C++代码）

图形输出 （Java代码）

C语言训练-素数问题 （C语言代码）

C二级辅导-同因查找 （C语言代码）

C语言训练-求函数值 （C语言代码）

✔✔✔ 树的直径问题+DFS求解 [c++]

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C二级辅导-公约公倍 （C语言代码）

打水问题 （C语言代码）

C语言程序设计教程（第三版）课后习题6.2 （C语言代码）

C语言程序设计教程（第三版）课后习题5.6 （C语言代码）

蓝桥杯历届试题-翻硬币 （C++代码）

C语言程序设计教程（第三版）课后习题11.5 （C语言代码）

Tom数 （C语言代码）

C二级辅导-等差数列 （C语言代码）

C语言训练-自守数问题 （C语言代码）

明明的随机数（C++代码）

图形输出（Java代码）

C语言训练-素数问题（C语言代码）

C二级辅导-同因查找（C语言代码）

C语言训练-求函数值（C语言代码）

　　评论区

C二级辅导-公约公倍（C语言代码）

打水问题（C语言代码）

蓝桥杯历届试题-翻硬币（C++代码）

Tom数（C语言代码）

C二级辅导-等差数列（C语言代码）

C语言训练-自守数问题（C语言代码）