蓝桥杯历届试题大臣的旅费（两次dfs 之树上求最长路径）

﹏ヽ暗。殇╰゛Y 2024-02-17 19:44 55阅读 0赞

分析：这题刚开始用一个二维数组储存从城市i到城市j，dfs很容易就写出来，但是只得了 75分，原因据说是最后一组数据在10000左右，二维数组明显开不下；好吧，就用vector容器来储存，但是呢我又采用的是把每个点都进行dfs遍历，这个做法就超时了，看了网上一些题解，原来只需要用两个点进行dfs遍历，首先任意找一个点，进行dfs找到最长路径，把端点记下，然后再从该端点进行dfs，得到的最长路就是要求的路径。细读题目会发现是一个树型的图，从任意一个城市i到任意城市j只有唯一一条路径（当然，不能重复经过），然后再附上别人写的树的直径（最长路）证明

主要是利用了反证法：

假设 s-t这条路径为树的直径，或者称为树上的最长路

现有结论，从任意一点u出发搜到的最远的点一定是s、t中的一点，然后在从这个最远点开始搜，就可以搜到另一个最长路的端点，即用两遍广搜就可以找出树的最长路

证明：

1 设u为s-t路径上的一点，结论显然成立，否则设搜到的最远点为T则

dis(u,T) >dis(u,s) 且 dis(u,T)>dis(u,t) 则最长路不是s-t了，与假设矛盾

2 设u不为s-t路径上的点

首先明确，假如u走到了s-t路径上的一点，那么接下来的路径肯定都在s-t上了，而且终点为s或t，在1中已经证明过了

所以现在又有两种情况了：

1：u走到了s-t路径上的某点，假设为X，最后肯定走到某个端点，假设是t ，则路径总长度为dis(u,X)+dis(X,t)

2：u走到最远点的路径u-T与s-t无交点，则dis(u-T) >dis(u,X)+dis(X,t);显然，如果这个式子成立，

则dis(u,T)+dis(s,X)+dis(u,X)>dis(s,X)+dis(X,t)=dis(s,t)最长路不是s-t矛盾

AC代码：

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<vector>
    using namespace std;
    const int maxn=1e5+10;
    
    struct node{
    	int to,cost;  //to表示到达的城市，cost表示走的路程
    	node(int to=0,int cost=0):to(to),cost(cost){}
    };
    int vis[maxn];
    int n;
    vector<node>vec[maxn];
    int tmp;
    int ans=0;
    
    void dfs(int i,int x){
    	if(ans<x)ans=x,tmp=i;
    	for(int j=0;j<vec[i].size();j++){
    		int t=vec[i][j].to;
    		int cost=vec[i][j].cost;
    		if(!vis[t]){
    			vis[t]=1;
    		    dfs(t,x+cost);
    		    vis[t]=0;
    	 }
    	}
    }
    int main(){
    	while(scanf("%d",&n)==1){
    		for(int i=1;i<=n;i++)
    		 vec[i].clear();
    		 
    		memset(vis,0,sizeof(vis));
    	    for(int i=1;i<=n-1;i++){
    	   	int a,b,c;
    	   	scanf("%d%d%d",&a,&b,&c);
    	   	vec[a].push_back(node(b,c));
    	   	vec[b].push_back(node(a,c));
    	   }
    	   
    	   tmp=1;
    	   vis[1]=1;
           dfs(1,0);
           
           memset(vis,0,sizeof(vis));
           vis[tmp]=1;
           ans=0;
           dfs(tmp,0);
    	   
    	   printf("%d\n",(1+10)*ans+ans*(ans-1)/2);
    	}
    	return 0;
    }