阿拉丁

用户名：uq_28080155906

访问量：1368

签　名：

等　　级
排　　名	10708
经　　验	1073
参赛次数	6
文章发表	2
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

邻接表两次DFS求树的直径(不会内存超限)
浏览：83

你可能喜欢

邻接表两次DFS求树的直径(不会内存超限)

　　作者: 阿拉丁　　　　发表时间：2022-10-30 13:10:37 浏览：83　|　评论：1　

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

package lqb.fs;

import java.util.ArrayList;
import java.util.Scanner;

//树的直径使用两次df来求:第一次用dfs从根节点求所到达的最大路径的根节点,第二次从第一次到达的根节点出发求最大路径即为树的直径
//使用邻接矩阵会内存超限所以使用邻接表

public class 大臣的旅费plusplus {

//节点数
    public static int N;
    //dfs访问标记
    public static int vis[];
    //第一次最大路径值
    private static int max;
    //第一次最大路径的叶子节点
    public static int rear=0;

//邻接表
    public static ArrayList<Node> arrayList[];

//表节点
    public static class Node{
        int adjvex; //下一个节点的位置
        int info;   //到下一个节点的距离

public Node(int adjvex, int info) {
            this.adjvex = adjvex;
            this.info = info;
        }
    }

public static void main(String[] args) {

//初始化
            Scanner scanner = new Scanner(System.in);
            N = scanner.nextInt();
            arrayList=new ArrayList[N+1];
            vis=new int[N+1];
            vis[1]=1;
            max=0;
            for (int i = 1; i <=N; i++) {
                arrayList[i]=new ArrayList<Node>();
            }
            for (int i = 1; i < N; i++) {
                int a = scanner.nextInt();
                int b = scanner.nextInt();
                int s = scanner.nextInt();
                arrayList[a].add(new Node(b,s));
                arrayList[b].add(new Node(a,s));
            }

dfs(1,0);
        vis[1]=0;
        vis[rear]=1;
        dfs(rear,0);

System.out.println((int)(max*10+(1+max)/2.0*max));

}

static void dfs(int r,int w){

for (Node node:arrayList[r]){
                if (vis[node.adjvex]==0) {
                    vis[node.adjvex] = 1;
                    if (w+node.info>max){
                        max=w+node.info;
                        rear=node.adjvex;
                    }
                    dfs(node.adjvex, w + node.info);
                    vis[node.adjvex] = 0;
                }
            }

}

0.0分

4 人评分

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

　　评论区

孤岛

写的很好

2022-10-30 13:11:53

阿拉丁

TA的其他文章

你可能喜欢

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

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

母牛的故事（C语言代码）

假币问题（C语言代码）

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

邻接表两次DFS求树的直径(不会内存超限)

评论区

精彩推荐

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

点我有惊喜！你懂得！

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

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

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

printf基础练习2 （C语言代码）

打水问题（C语言代码）

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

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

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

阿拉丁

TA的其他文章

你可能喜欢

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

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

母牛的故事 （C语言代码）

假币问题 （C语言代码）

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

邻接表两次DFS求树的直径(不会内存超限)

评论区

精彩推荐

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

点我有惊喜！你懂得！

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

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

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

printf基础练习2 （C语言代码）

打水问题 （C语言代码）

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

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

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

母牛的故事（C语言代码）

假币问题（C语言代码）

　　评论区

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

打水问题（C语言代码）

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