蓝桥杯双周赛算法心得——串门（双链表数组+双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--;}//开始第一次的dfsdfs(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（回溯）

---

试题链接：