蓝桥杯大臣的旅费 JAVA

思路:该题要使用树的直径。

求树的直径:先从一个点DFS，找到一个最远的点v，然后以该点v作为起点再次DFS，找到点t，则v到t则为该树的最远直径。

 1 import java.util.Arrays;
 2 import java.util.Scanner;
 3 
 4 public class 大臣的旅费 {
 5     
 6     public static int ans = Integer.MIN_VALUE;
 7     public static int temp,n;
 8     public static boolean[] visited = new boolean[7010];
 9     public static int[][] map = new int[7010][7010];
10     
11     public static void main(String[] args) {
12         Scanner sc = new Scanner(System.in);
13         n = sc.nextInt();
14         sc.nextLine();
15         
16         for(int i=0;i<n-1;i++){
17             int x = sc.nextInt()-1;
18             int y = sc.nextInt()-1;
19             int dis = sc.nextInt();
20             
21             map[x][y] = dis;
22             map[y][x] = dis;
23         }
24         
25         visited[0] = true;
26         DFS(0,0);
27         Arrays.fill(visited, false);
28         
29         visited[temp] = true;
30         ans = Integer.MIN_VALUE;
31         DFS(temp, 0);//第二次深度优先搜索
32 
33         //System.out.println(ans);
34         int sum = (11+10+ans)*ans/2;
35         System.out.println(sum);
36     }
37     
38     
39     public static void DFS(int start,int dist){//起点，距离
40         if(dist>ans){
41             ans = dist;
42             temp = start;
43         }
44         for(int i=0;i<n;i++){
45             if(!visited[i]&&map[start][i]>0){
46                 visited[i] = true;
47                 dist+= map[start][i];
48                 DFS(i, dist);
49                 visited[i] = false;
50                 dist -= map[start][i];
51             }
52         }
53         return;
54     }
55 }

蓝桥杯 大臣的旅费 JAVA

蓝桥杯大臣的旅费 JAVA