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

大家好，我是晴天学长，树和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;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

---

4）.总结

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

---

试题链接：