小哈哈

用户名：20180390139

访问量：19733

签　名：

世界上怎么会有那么聪明的人呢？

等　　级
排　　名	216
经　　验	6368
参赛次数	9
文章发表	38
年　　龄	0
在职情况	学生
学　　校	蓝翔挖掘机技校
专　　业	网络工程

　　自我简介：

我是个傻嗨，但是我会努力像个正常人

TA的其他文章

吹哨传球-题解(C语言代码)----------------动态规划
浏览：551

我要送人头！-题解(C语言代码)------就这样，线性代数里面有过
浏览：430

P1016-题解(C语言代码)------动态规划，通俗详细描述
浏览：580

你可能喜欢

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

蓝桥杯2013年第四届真题-大臣的旅费-题解(C++代码)--------------------重点是这个结论，知道后就很简单了

　　作者: 小哈哈　　　　发表时间：2020-04-19 16:11:52 浏览：398　|　评论：0　

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

这道题是“树的直径”经典模板题，解题的关键是这个结论：
	
注：树的直径是指：这棵树上最长的一条路径*****************
#：在这棵树上，从任意一点出发到离它最远的点，把这个点记为A，那么A点就是这棵树直径的某一个端点。
	
	我们这道题不就是找树上的  最长的路径   的长度吗
	
	那么上面的结论就可以用到了，我们要找这最长的路径要怎么找呢
	1、先找到这个最长的路径的某一个端点，记为 ID
	2、再由这个端点ID出发，找离  ID点  最远的点，找到的这个点肯定是 树的直径  的另一个端点啊
	
	那么最长的路径不久确定了吗
	
	本题的解法是，先写一个dfs函数，它的功能是：找到从某一个点出发，到离它最远的点，然后顺便把距离也记住，而且也把这个点记住，用变量ID存储
	
	接下来再调用一次dfs不就把另一个端点求出来了吗
	
	#include<iostream>
    #include<vector>
    #include<bits/stdc++.h>
    using namespace std;
    #define N 10001
    
    long long max0=-1e15;
    int ID;
    vector<int> v[N];
    vector<int> T[N];
    int book[N]={0};
    
    int sum[N]={0};
    
    long long cnt( int x,int sum ){
    	
    	long long ans;
    	ans=( x+sum )*( sum-x+1 );
    	ans/=2;
    	return ans;
    }
    void dfs( int cur,long long step ){
    	
    	
    	
    	if( step>max0 ){
    		
    		max0=step;
    		ID=cur;
    		
    	}
    	
    	int i;
    	for(i=0;i<v[cur].size();i++){
    		
    		int t=v[cur][i];
    		if( book[ t ]==1 )
    		continue;
    		
    		book[t]=1;
    		dfs( t , step+T[cur][i] );
    		book[t]=0;
    	}
    	
    	return ;
    }
    int main(     ){
    	
    	int i,j,k;
    	int n;
    	
    	scanf("%d",&n);
    	
    	
    	for(i=1;i<n;i++){
    		int x,y,z;
    		scanf("%d%d%d",&x,&y,&z);
    		v[x].push_back( y );//这是邻接表存储，对于x这个点，我要记录它可以到哪些点呢，然后把能到的点push进去
			
    		v[y].push_back( x );
    		//因为是无向图，所以要反过来记录一次
			
    		T[x].push_back( z );//T[x]这个东西是顺便记录长度的
			//同步记录，比如T[x][j]和v[x][j]对应，表示x到j这个点的长度
    		T[y].push_back( z );
    	}
    	
    	
    	book[1]=1;
    	dfs( 1,0 );//上面也说了，我们要找 树的直径的一个端点先，那就从任意一个点出发去找，这里就从1出发，你也可以从其他点出发
    	book[1]=0;
    	
    	max0=-1e15;
    	
    	book[ID]=1; //好了，我们刚刚记录了 树的直径  的某一个端点ID，那么，就从ID点开始找另一个端点，然后顺便记录离它最远的点的长度
    	dfs( ID,0 );
    	
    	cout<<cnt(1+10,max0+10)<<endl;  //接下来对应求出花费就行了
    	return 0;
    }

0.0分

1 人评分

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

小哈哈

TA的其他文章

你可能喜欢

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

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

C二级辅导-求偶数和（C++代码）

【计算两点间的距离】（C语言代码）

【绝对值排序】（C语言代码）

蓝桥杯2013年第四届真题-大臣的旅费-题解(C++代码)--------------------重点是这个结论，知道后就很简单了

评论区

精彩推荐

K-进制数（C++代码）

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

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C++代码）（手动优化一下计算）

C语言训练-角谷猜想（C语言代码）

回文串（C语言代码）

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

【金明的预算方案】（C++代码）

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

核桃的数量（C语言代码）

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

小哈哈

TA的其他文章

你可能喜欢

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

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

C二级辅导-求偶数和 （C++代码）

【计算两点间的距离】 （C语言代码）

【绝对值排序】 （C语言代码）

蓝桥杯2013年第四届真题-大臣的旅费-题解(C++代码)--------------------重点是这个结论，知道后就很简单了

评论区

精彩推荐

K-进制数 （C++代码）

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

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值 （C++代码）（手动优化一下计算）

C语言训练-角谷猜想 （C语言代码）

回文串 （C语言代码）

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

【金明的预算方案】 （C++代码）

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

核桃的数量 （C语言代码）

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

C二级辅导-求偶数和（C++代码）

【计算两点间的距离】（C语言代码）

【绝对值排序】（C语言代码）

　　评论区

K-进制数（C++代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C++代码）（手动优化一下计算）

C语言训练-角谷猜想（C语言代码）

回文串（C语言代码）

【金明的预算方案】（C++代码）

核桃的数量（C语言代码）