題目鏈接：?1299: 結(jié)點(diǎn)選擇

參考：?【Java】 藍(lán)橋杯ALGO-4 算法訓(xùn)練 結(jié)點(diǎn)選擇——柳婼 の blog

Description

有一棵n個(gè)節(jié)點(diǎn)的樹，樹上每個(gè)節(jié)點(diǎn)都有一個(gè)正整數(shù)權(quán)值。如果一個(gè)點(diǎn)被選擇了，那么在樹上和它相鄰的點(diǎn)都不能被選擇。求選出的點(diǎn)的權(quán)值和最大是多少？

Input

多組測(cè)試數(shù)據(jù)
每組第一行包含一個(gè)整數(shù)n。
接下來的一行包含n個(gè)正整數(shù)，第i個(gè)正整數(shù)代表點(diǎn)i的權(quán)值。
接下來一共n-1行，每行描述樹上的一條邊。

Output

輸出一個(gè)整數(shù)，代表選出的點(diǎn)的權(quán)值和的最大值。

Simple Input

5 1 2 3 4 5 1 2 1 3 2 4 2 5

Sample Output

12

Hint

樣例說明
選擇3、4、5號(hào)點(diǎn)，權(quán)值和為 3+4+5 = 12 。

數(shù)據(jù)規(guī)模與約定
對(duì)于20%的數(shù)據(jù)， n <= 20。
對(duì)于50%的數(shù)據(jù)， n <= 1000。
對(duì)于100%的數(shù)據(jù)， n <= 100000。
權(quán)值均為不超過1000的正整數(shù)。

分析?

樹的存儲(chǔ)結(jié)構(gòu)原本可以用“孩子表示法”，可是此題的輸入并不是先父結(jié)點(diǎn)后子結(jié)點(diǎn)，因此，我們不妨用無(wú)向圖來看待此樹（樹其實(shí)也是圖）。而此題結(jié)點(diǎn)數(shù)比較大，用“數(shù)組表示法”顯然不合適（內(nèi)存可能不夠），“十字鏈表”和“鄰接多重表”則比較繁瑣，“鄰接表”作為存儲(chǔ)結(jié)構(gòu)最為合適。

采用先序遍歷的算法遍歷整棵樹。

當(dāng)前子樹的根結(jié)點(diǎn)可以選擇，可以不選擇。
如果根結(jié)點(diǎn)不選擇，那么它的某個(gè)子結(jié)點(diǎn)可不選擇，也可選擇。只需選取其中權(quán)值較大的那種加到根結(jié)點(diǎn)的權(quán)值中即可。
如果根結(jié)點(diǎn)選擇，那么它的所有子結(jié)點(diǎn)都不能選擇。也就是將子結(jié)點(diǎn)不選擇的那種的權(quán)值加到根結(jié)點(diǎn)權(quán)值中即可。

不選擇當(dāng)前子樹的根結(jié)點(diǎn)，那么就將它的子結(jié)點(diǎn)（子樹）i的權(quán)值較大的情況加到根結(jié)點(diǎn)中
weight[root][0] += Math.max(weight[i][0], weight[i][1]);
選擇當(dāng)前子樹的根結(jié)點(diǎn)，那么將它的子結(jié)點(diǎn)（子樹）i的不選擇的權(quán)值加到根結(jié)點(diǎn)中
weight[root][1] += weight[i][0];

代碼?

/*** Time 3505ms* @author wowpH* @version 1.1* @date 2019年6月7日上午10:57:35* Environment: Windows 10* IDE Version: Eclipse 2019-3* JDK Version: JDK1.8.0_112*/import java.io.InputStreamReader; import java.util.ArrayList; import java.util.List; import java.util.Scanner;public class Main {private Scanner sc;private static final int MAX_N = 100001;private int n;private int[][] weight;// 權(quán)值private List<List<Integer>> adjacencyList;// 鄰接表public Main() {weight = new int[MAX_N][2];// 下標(biāo)從1開始sc = new Scanner(new InputStreamReader(System.in));while (sc.hasNext()) {adjacencyList = new ArrayList<List<Integer>>();// 頭指針的線性表input();dfs(1, 0);// 1根節(jié)點(diǎn)，0無(wú)前驅(qū)結(jié)點(diǎn)System.out.println(Math.max(weight[1][0], weight[1][1]));}sc.close();}private void input() {n = sc.nextInt();// 結(jié)點(diǎn)數(shù)adjacencyList.add(new ArrayList<Integer>());// 下標(biāo)從1開始，這個(gè)不用for (int i = 1; i <= n; i++) {weight[i][0] = 0; // 初始化為0weight[i][1] = sc.nextInt();// 輸入權(quán)值adjacencyList.add(new ArrayList<Integer>());// 創(chuàng)建頭結(jié)點(diǎn)}int head, tail;// 弧的頭尾for (int i = 1; i < n; i++) {tail = sc.nextInt();head = sc.nextInt();adjacencyList.get(tail).add(head);// 添加表結(jié)點(diǎn)adjacencyList.get(head).add(tail);// 無(wú)向圖，添加表結(jié)點(diǎn)}}private void dfs(int root, int pre) {// root根，pre前驅(qū)結(jié)點(diǎn)List<Integer> list = adjacencyList.get(root);// 當(dāng)前鏈表for (Integer i : list) {if (i != pre) {// 非葉子結(jié)點(diǎn)，繼續(xù)向下遞歸dfs(i, root);// 不選root點(diǎn)，選root子結(jié)點(diǎn)i最大的情況weight[root][0] += Math.max(weight[i][0], weight[i][1]);// 選root點(diǎn)，不選root子結(jié)點(diǎn)i的情況weight[root][1] += weight[i][0];}}}public static void main(String[] args) {new Main();} }

轉(zhuǎn)載于:https://www.cnblogs.com/wowpH/p/11060764.html

總結(jié)

以上是生活随笔為你收集整理的WUSTOJ 1299: 结点选择（Java）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。