蓝桥杯双周赛算法心得——串门（双链表数组+双dfs）-CSDN博客

大家好我是晴天学长树和dfs的结合其邻接表的存图方法也很重要。需要的小伙伴可以关注支持一下哦后续会继续更新的。

---

1) .串门

---

2) .算法思路

串门怎么存图很关键
用双链表存
1.找到最长的那段路树的最长直径
2.答案=总和*2-最长那段路。

1.接受数据
2.建立标记数组存图
3.从1开始找最大路径并更新最大路径的点
4.从最大路径的点开始出发再找最大路径
5.答案

---

3.算法步骤

1.读取输入的节点数量 n。
2.创建一个布尔数组 vis用于记录节点的访问状态。
3.初始化变量 total 为节点数量 n。
4.将 n 减 1并创建一个链表列表 list用于存储图的边关系。
5.循环 n 次读取边的起点 u、终点 v 和权重 w。
6.将路径和增加 w + w。
7.在 list 中的起点 u 处添加边的信息 [v, w]。
8.在 list 中的终点 v 处添加边的信息 [u, w]。
9.调用 dfs 方法进行第一次深度优先搜索参数为起点 1访问状态数组 vis 和初始路径和 0。
10.重置访问状态数组 vis 为初始状态最大路径和 maxsum 为 0。
11.调用 dfs 方法进行第二次深度优先搜索参数为节点编号 nodeindex访问状态数组 vis 和初始路径和 0。
12.计算最终结果输出 totalsum - maxsum。

---

4. 代码实例

package LanQiaoTest.DFS;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;

public class 串门 {
    static List<List<int[]>> list = new ArrayList<>();
    static long maxsum = 0;
    static int nodeindex = 0;
    static long totalsum = 0;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        boolean[] vis = new boolean[n + 10];
        int total = n ;
        n--;
        //建立链表
        for (int i = 0; i < n + 10; i++) {
            list.add(new ArrayList<>());
        }
        //接受数据,存图树
        while (n > 0) {
            int u = scanner.nextInt();
            int v = scanner.nextInt();
            int w = scanner.nextInt();
            //添加路径和
            totalsum += w + w;
            // 两个路径都可以走
            list.get(u).add(new int[]{v, w});
            list.get(v).add(new int[]{u, w});
            n--;
        }
        //开始第一次的dfs
        dfs(1, vis, 0);
        //第一次结束开始第二次
        vis = new boolean[total + 10];
        maxsum = 0;
        // 开始找第二次
        dfs(nodeindex, vis, 0);
        System.out.println(totalsum - maxsum);
    }

    public static void dfs(int start, boolean[] vis, long sum) {
        //避免往回走
        vis[start] = true;
        if (sum > maxsum) {
            maxsum = sum;
            nodeindex = start;
        }
        //开枝散叶
        for (int i = 0; i < list.get(start).size(); i++) {
            int[] temp = list.get(start).get(i);
            //没有标记,就走下去
            if (!vis[temp[0]]) {
                dfs(temp[0], vis, sum+temp[1]);
            }
        }
        //也可以不回溯因为跟随着的是返回结果不会在重复的走下去了回溯也行。
        vis[start]=false;
    }
}

---

4.总结

• 图树的正确遍历。
• dfs回溯

---

试题链接