生命之樹

在X森林里，上帝創建了生命之樹。
他給每棵樹的每個節點（葉子也稱為一個節點）上，都標了一個整數，代表這個點的和諧值。
上帝要在這棵樹內選出一個非空節點集S，使得對于S中的任意兩個點a,b，都存在一個點列 {a, v1, v2, …, vk, b} 使得這個點列中的每個點都是S里面的元素，且序列中相鄰兩個點間有一條邊相連。
在這個前提下，上帝要使得S中的點所對應的整數的和盡量大。
這個最大的和就是上帝給生命之樹的評分。
經過atm的努力，他已經知道了上帝給每棵樹上每個節點上的整數。但是由于 atm 不擅長計算，他不知道怎樣有效的求評分。他需要你為他寫一個程序來計算一棵樹的分數。

「輸入格式」
第一行一個整數 n 表示這棵樹有 n 個節點。
第二行 n 個整數，依次表示每個節點的評分。
接下來 n-1 行，每行 2 個整數 u, v，表示存在一條 u 到 v 的邊。由于這是一棵樹，所以是不存在環的。

「輸出格式」
輸出一行一個數，表示上帝給這棵樹的分數。

「樣例輸入」
5
1 -2 -3 4 5
4 2
3 1
1 2
2 5

「樣例輸出」
8

「數據范圍」
對于 30% 的數據，n <= 10
對于 100% 的數據，0 < n <= 10^5, 每個節點的評分的絕對值不超過 10^6 。
資源約定：
峰值內存消耗（含虛擬機） < 256M
CPU消耗 < 3000ms
請嚴格按要求輸出，不要畫蛇添足地打印類似：“請您輸入…” 的多余內容。
所有代碼放在同一個源文件中，調試通過后，拷貝提交該源碼。
注意：不要使用package語句。不要使用jdk1.7及以上版本的特性。
注意：主類的名字必須是：Main，否則按無效代碼處理。

解析：我們簡要分析之后可以發現這是一棵無向賦權圖，要求是尋找一棵最大的生成樹。這里采用dfs()+松弛進行求解。
v數組代表每個節點的評分，如果從 i 節點與 j 節點的權值和大于 i 結點本身的權值，那么更新i結點的權值，直達找出一條能夠連接權值最大的路徑。

import java.util.Scanner;public class Main {static int n;static int[] v;static int[][] arr;static boolean[] vis;static int max = 0;public static void main(String[] args) {Scanner in = new Scanner(System.in);n = in.nextInt();v = new int[n+1];arr = new int[n+1][n+1];vis = new boolean[n+1];for (int i = 1; i <= n; i++) {v[i] = in.nextInt();}for (int i = 1; i < n; i++) {int a = in.nextInt();int b = in.nextInt();arr[a][b] = 1;arr[b][a] = 1;}dfs(1);System.out.println(max);}private static void dfs(int m) {vis[m] = true;for (int i = 1; i <= n; i++) {if (vis[i] == false && arr[m][i] != 0) {dfs(i);if (v[m] < (v[m] + v[i])) {v[m] = v[m] +v[i];}max = Math.max(max, v[m]);}}} }

總結

以上是生活随笔為你收集整理的蓝桥杯第六届省赛JAVA真题----生命之树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。