devbox
2023面试高手
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

蓝桥杯结点选择（树形动态规划）_蓝桥杯树上选点

作者：2023面试高手 | 2024-02-06 19:22:40

赞

踩

蓝桥杯树上选点

这道题就是一道树的最大独立集问题。先看一下题目要求：

问题描述
有一棵 n 个节点的树，树上每个节点都有一个正整数权值。如果一个点被选择了，那么在树上和它相邻的点都不能被选择。求选出的点的权值和最大是多少？


输入格式
第一行包含一个整数 n 。


接下来的一行包含 n 个正整数，第 i 个正整数代表点 i 的权值。


接下来一共 n-1 行，每行描述树上的一条边。


输出格式
输出一个整数，代表选出的点的权值和的最大值。
样例输入
5
1 2 3 4 5
1 2
1 3
2 4
2 5
样例输出
12
样例说明
选择3、4、5号点，权值和为 3+4+5 = 12 。
数据规模与约定
对于20%的数据， n <= 20。


对于50%的数据， n <= 1000。


对于100%的数据， n <= 100000。


权值均为不超过1000的正整数。


好的那么我们看一下解决思路：

首先一定是要接收输入的值，

再者就是把结点相连，构建成树。

题目告诉不一定是二叉树，所以可以看做图来处理

可以使用邻接表存储建立一个数组tree[i][j]表示结点i的第j个孩子结点

dp[i][0]表示不取i结点的结果

dp[i][1]表示取i结点的结果

用深度优先搜索和动态规划，每个点的最大权值有两种情况，取和不取该结点，如果取了这个结点，哪么与它相邻的点就不能取了；不取当前点则取与他相邻点的最大值进行累加，从底向上累加到顶部：max（dp[i][1],dp[i][0]）就是要求的结果。

用一个变量root保存当前结点的前一个结点，如果等于了root说明访问到了它的父亲结点，为了防止重复访问，要在tree[start][i]不等于root时候继续dfs下去，否则，可能成为无限循环的环。

思路就是这样，让我们一起撸代码吧！

  1. import java.util.Scanner;
  2.  
  3. public class Main {
  4.     public int[][] dp = new int[100002][2];   
  5.     public int[][] tree = new int[100002][300];  //tree[i][3] = num表示第i个节点的第3个孩子节点为第num个节点
  6.     /*
  7.      * 参数point1:表示输入的第point1个节点，不是节点权值
  8.      * 参数point2:表示输入的第point2的节点，不是节点权值
  9.      * 采用邻接表来存储数据的值。
  10.      */
  11.     public void creatTree(int point1, int point2) {
  12.         int i = 0;
  13.         //当第point1个节点为父母节点时
  14.         while(tree[point1][i] != 0) i++;  //如果第point1个节点已经有孩子了，再增加一个孩子  
  15.         tree[point1][i] = point2;
  16.         int j = 0;
  17.         //当第point2个节点为父母节点时
  18.         while(tree[point2][j] != 0) j++;
  19.         tree[point2][j] = point1;
  20.     }
  21.     /*
  22.      * 参数satrt:开始对树进行DFS遍历的开始节点，为具体节点位置，不是节点权值
  23.      * 参数root:为第start个节点的直接父母节点位置，root = 0表示根节点的父母节点
  24.      */
  25.     public void dfs(int start, int root) {
  26.         int child = tree[start][0];  //第start个节点的第1个孩子节点
  27.         for(int i = 0;child != 0;i++) {
  28.             child = tree[start][i];
  29.             if(child != root) {  //防止出现start的孩子成为start的父亲情况
  30.                 dfs(child, start);
  31.                 dp[start][1] += dp[child][0]; 
  32.                 dp[start][0] += (dp[child][1] > dp[child][0] ? dp[child][1] : dp[child][0]);
  33.             }
  34.         }
  35.     }
  36.     
  37.     public static void main(String[] args) {
  38.         Main test = new Main();
  39.         Scanner in = new Scanner(System.in);
  40.         int n = in.nextInt();
  41.         for(int i = 0;i < n;i++)
  42.             test.dp[i + 1][1] = in.nextInt();
  43.         for(int i = 0;i < n - 1;i++) {
  44.             int point1 = in.nextInt();
  45.             int point2 = in.nextInt();
  46.             test.creatTree(point1, point2);
  47.         }
  48.         test.dfs(1, 0);   //从创建的数的根节点（即第1个顶点，0表示根节点的父母节点）开始进行DFS遍历
  49.         int max = (test.dp[1][1] > test.dp[1][0] ? test.dp[1][1] : test.dp[1][0]);
  50.         System.out.println(max);
  51.     }
  52. }

从运行结果来看，这道题是正确的。

但是提交之后，是超时的只得了50分，所以，还需要改进。

搜索了一下超时的原因：说是Scanner效率太低，所以使用了BufferedReader+StringTokenizer的方法依然超时。

  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStreamReader;
  4. import java.util.Scanner;
  5. import java.util.StringTokenizer;
  6.  
  7. public class Main {
  8.     public int[][] dp = new int[100002][2];   
  9.     public int[][] tree = new int[100002][300];  //tree[i][3] = num表示第i个节点的第3个孩子节点为第num个节点
  10.     /*
  11.      * 参数point1:表示输入的第point1个节点，不是节点权值
  12.      * 参数point2:表示输入的第point2的节点，不是节点权值
  13.      * 说明：由于题目仅仅给出边的说明，并未说明两个节点谁是父母节点，所以以下有两种情形
  14.      */
  15.     public void creatTree(int point1, int point2) {
  16.         int i = 0;
  17.         //当第point1个节点为父母节点时
  18.         while(tree[point1][i] != 0) i++;  //如果第point1个节点已经有孩子了，再增加一个孩子  
  19.         tree[point1][i] = point2;
  20.         int j = 0;
  21.         //当第point2个节点为父母节点时
  22.         while(tree[point2][j] != 0) j++;
  23.         tree[point2][j] = point1;
  24.     }
  25.     /*
  26.      * 参数satrt:开始对树进行DFS遍历的开始节点，为具体节点位置，不是节点权值
  27.      * 参数root:为第start个节点的直接父母节点位置，root = 0表示根节点的父母节点
  28.      */
  29.     public void dfs(int start, int root) {
  30.         int child = tree[start][0];  //第start个节点的第1个孩子节点
  31.         for(int i = 0;child != 0;i++) {
  32.             child = tree[start][i];
  33.             if(child != root) {  //防止出现start的孩子成为start的父亲情况
  34.                 dfs(child, start);
  35.                 dp[start][1] += dp[child][0];  
  36.                 dp[start][0] += (dp[child][1] > dp[child][0] ? dp[child][1] : dp[child][0]);
  37.             }
  38.         }
  39.     }
  40.     
  41.     public static void main(String[] args) throws IOException {
  42.         Main test = new Main();
  43.         //Scanner in = new Scanner(System.in);
  44.         BufferedReader reader=new BufferedReader(new InputStreamReader(System.in));
  45.         
  46.         String input=reader.readLine();
  47.         int n =	Integer.parseInt(input);
  48.         String input1=reader.readLine();
  49.         StringTokenizer tok0=new StringTokenizer(input1);
  50.         for(int i = 0;i < n;i++) {
  51.             test.dp[i + 1][1] = Integer.valueOf(tok0.nextToken());
  52.         }
  53.         for(int i = 0;i < n - 1;i++) {
  54.         	String input2=reader.readLine();
  55.         	StringTokenizer tok=new StringTokenizer(input2);
  56.             int point1=Integer.valueOf(tok.nextToken());
  57.             int point2=Integer.valueOf(tok.nextToken());
  58.             test.creatTree(point1, point2);
  59.         }
  60.         test.dfs(1, 0);   //从创建的数的根节点（即第1个顶点，0表示根节点的父母节点）开始进行DFS遍历
  61.         int max = (test.dp[1][1] > test.dp[1][0] ? test.dp[1][1] : test.dp[1][0]);
  62.         System.out.println(max);
  63.     }
  64. }
在网上找到一个AC了的代码，分析一下代码的缺陷在哪， 
  1. import java.io.*;
  2. import java.util.*;
  3.  
  4. public class Main {
  5. 	
  6. 	final static int MAX_N = 100010;
  7.  
  8. 	PrintWriter out;
  9. 	InputReader cin;
  10. 	int edgecnt;
  11. 	int dp[][] = new int[MAX_N][2];
  12. 	Edge E[] = new Edge[MAX_N * 2];
  13. 	int head[] = new int[MAX_N];
  14. 	int sta[] = new int[MAX_N * 2];
  15. 	boolean vis[] = new boolean[MAX_N];
  16. 	
  17. 	class Edge {
  18. 		int u, v, nxt;
  19. 		Edge () {
  20. 			
  21. 		}
  22. 		Edge (int _u, int _v, int _n) {
  23. 			u = _u;
  24. 			v = _v;
  25. 			nxt = _n;
  26. 		}
  27. 	}
  28. 	class InputReader {
  29. 		InputReader(InputStream in) {
  30. 			reader = new BufferedReader(new InputStreamReader(in));
  31. 			tokenizer = new StringTokenizer("");
  32. 		}
  33.  
  34. 		private String next() throws IOException {
  35. 			while (!tokenizer.hasMoreTokens()) {
  36. 				tokenizer = new StringTokenizer(reader.readLine());
  37. 			}
  38. 			return tokenizer.nextToken();
  39. 		}
  40.  
  41. 		public Integer nextInt() throws IOException {
  42. 			return Integer.parseInt(next());
  43. 		}
  44. 		private BufferedReader reader;
  45. 		private StringTokenizer tokenizer;
  46. 	}
  47.  
  48. 	
  49. 	void add(int u, int v) {
  50. 		E[edgecnt] = new Edge(u, v, head[u]);
  51. 		head[u] = edgecnt++;
  52. 	}
  53. 	
  54. 	void dfs(int x, int fa) {
  55. 		Arrays.fill(vis, false);
  56. 		int top = 0;
  57. 		vis[x] = true;
  58. 		sta[top++] = x;
  59. 		while (top > 0) {
  60. 			int u = sta[top - 1];
  61. 			boolean Ed = false;
  62. 			for (int i = head[u]; i + 1 != 0; i = E[i].nxt) {
  63. 				int v = E[i].v;
  64. 				if (vis[v]) continue;
  65. 				Ed = true;
  66. 				sta[top++] = v;
  67. 				vis[v] = true;
  68. 			}
  69. 			if (Ed) continue;
  70. 			--top;
  71. 			for (int i = head[u]; i + 1 != 0; i = E[i].nxt) {
  72. 				int v = E[i].v;
  73. 				dp[v][0] += Math.max(dp[u][0], dp[u][1]);
  74. 				dp[v][1] += dp[u][0];
  75. 				
  76. 			}
  77. 		}
  78. 	}
  79. 	
  80. 	void run() throws IOException {
  81. 		int n = cin.nextInt();
  82. 		
  83. 		for (int i = 1; i <= n; ++i) 
  84. 			dp[i][1] = cin.nextInt();
  85. 		Arrays.fill(head, -1);
  86. 		for (int i = 1; i < n; ++i) {
  87. 			int u = cin.nextInt();
  88. 			int v = cin.nextInt();
  89. 			add(u, v);
  90. 			add(v, u);
  91. 		}
  92. 		dfs(1, -1);
  93. 		int ans = Math.max(dp[1][0], dp[1][1]);
  94. 		out.println(ans);
  95. 		out.close(); 
  96. 	}
  97.  
  98. 	public static void main(String[] args) throws IOException {
  99. 		new Main().run();
  100. 	}
  101.  
  102. 	Main() {
  103. 		cin = new InputReader(System.in);
  104. 		out = new PrintWriter(System.out);
  105. 	}
  106.  
  107. }
这是别人写的代码让我们看一下问题。

将代码改写成下面这样依然不行，说明在思路上除了问题

  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStream;
  4. import java.io.InputStreamReader;
  5. import java.io.PrintWriter;
  6. import java.util.StringTokenizer;
  7.  
  8. public class Main {
  9.     public  int[][] dp = new int[100002][2];   
  10.     public int[][] tree = new int[100002][300];  //tree[i][3] = num表示第i个节点的第3个孩子节点为第num个节点
  11.     PrintWriter out;
  12.     InputReader cin;
  13.     /*
  14.      * 参数point1:表示输入的第point1个节点，不是节点权值
  15.      * 参数point2:表示输入的第point2的节点，不是节点权值
  16.      * 说明：由于题目仅仅给出边的说明，并未说明两个节点谁是父母节点，所以以下有两种情形
  17.      */
  18.     public void creatTree(int point1, int point2) {
  19.         int i = 0;
  20.         //当第point1个节点为父母节点时
  21.         while(tree[point1][i] != 0) i++;  //如果第point1个节点已经有孩子了，再增加一个孩子  
  22.         tree[point1][i] = point2;
  23.         int j = 0;
  24.         //当第point2个节点为父母节点时
  25.         while(tree[point2][j] != 0) j++;
  26.         tree[point2][j] = point1;
  27.     }
  28.     /*
  29.      * 参数satrt:开始对树进行DFS遍历的开始节点，为具体节点位置，不是节点权值
  30.      * 参数root:为第start个节点的直接父母节点位置，root = 0表示根节点的父母节点
  31.      */
  32.     public void dfs(int start, int root) {
  33.         int child = tree[start][0];  //第start个节点的第1个孩子节点
  34.         for(int i = 0;child != 0;i++) {
  35.             child = tree[start][i];
  36.             if(child != root) {  //防止出现start的孩子成为start的父亲情况
  37.                 dfs(child, start);
  38.                 dp[start][1] += dp[child][0];  
  39.                 dp[start][0] += Math.max(dp[child][1], dp[child][0]);
  40.             }
  41.         }
  42.     }
  43.     void run() throws IOException {
  44.     	 int n =	cin.nextInt();
  45.          for(int i = 0;i < n;i++) {
  46.              dp[i + 1][1] = cin.nextInt();
  47.          }
  48.          for(int i = 0;i < n - 1;i++) {
  49.              int point1=cin.nextInt();
  50.              int point2=cin.nextInt();
  51.              creatTree(point1, point2);
  52.          }
  53.          dfs(1, 0);   //从创建的数的根节点（即第1个顶点，0表示根节点的父母节点）开始进行DFS遍历
  54.          int max = Math.max(dp[1][1], dp[1][0]);
  55.          out.println(max);
  56.          out.close();
  57. 	}
  58.     public static void main(String[] args) throws IOException {
  59.     	new Main().run();
  60.     }
  61.     
  62.     Main() {
  63. 		 cin = new InputReader(System.in);
  64. 		 out = new PrintWriter(System.out);
  65. 	}
  66.  
  67. 	class InputReader {
  68. 		InputReader(InputStream in) {
  69. 			reader = new BufferedReader(new InputStreamReader(in));
  70. 			tokenizer = new StringTokenizer("");
  71. 		}
  72.  
  73. 		private String next() throws IOException {
  74. 			while (!tokenizer.hasMoreTokens()) {
  75. 				tokenizer = new StringTokenizer(reader.readLine());
  76. 			}
  77. 			return tokenizer.nextToken();
  78. 		}
  79.  
  80. 		public Integer nextInt() throws IOException {
  81. 			return Integer.parseInt(next());
  82. 		}
  83. 		private BufferedReader reader;
  84. 		private StringTokenizer tokenizer;
  85. 	}
  86. }

路过的大神，帮帮忙！

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/2023面试高手/article/detail/64240
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号