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

小咪咪 2022-05-31 06:48 167阅读 0赞

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

问题描述  
有一棵 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下去，否则，可能成为无限循环的环。

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

import java.util.Scanner;
    
    public class Main {
        public int[][] dp = new int[100002][2];   
        public int[][] tree = new int[100002][300];  //tree[i][3] = num表示第i个节点的第3个孩子节点为第num个节点
        /*
         * 参数point1:表示输入的第point1个节点，不是节点权值
         * 参数point2:表示输入的第point2的节点，不是节点权值
         * 采用邻接表来存储数据的值。
         */
        public void creatTree(int point1, int point2) {
            int i = 0;
            //当第point1个节点为父母节点时
            while(tree[point1][i] != 0) i++;  //如果第point1个节点已经有孩子了，再增加一个孩子  
            tree[point1][i] = point2;
            int j = 0;
            //当第point2个节点为父母节点时
            while(tree[point2][j] != 0) j++;
            tree[point2][j] = point1;
        }
        /*
         * 参数satrt:开始对树进行DFS遍历的开始节点，为具体节点位置，不是节点权值
         * 参数root:为第start个节点的直接父母节点位置，root = 0表示根节点的父母节点
         */
        public void dfs(int start, int root) {
            int child = tree[start][0];  //第start个节点的第1个孩子节点
            for(int i = 0;child != 0;i++) {
                child = tree[start][i];
                if(child != root) {  //防止出现start的孩子成为start的父亲情况
                    dfs(child, start);
                    dp[start][1] += dp[child][0]; 
                    dp[start][0] += (dp[child][1] > dp[child][0] ? dp[child][1] : dp[child][0]);
                }
            }
        }
        
        public static void main(String[] args) {
            Main test = new Main();
            Scanner in = new Scanner(System.in);
            int n = in.nextInt();
            for(int i = 0;i < n;i++)
                test.dp[i + 1][1] = in.nextInt();
            for(int i = 0;i < n - 1;i++) {
                int point1 = in.nextInt();
                int point2 = in.nextInt();
                test.creatTree(point1, point2);
            }
            test.dfs(1, 0);   //从创建的数的根节点（即第1个顶点，0表示根节点的父母节点）开始进行DFS遍历
            int max = (test.dp[1][1] > test.dp[1][0] ? test.dp[1][1] : test.dp[1][0]);
            System.out.println(max);
        }
    }

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

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

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

import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    import java.util.Scanner;
    import java.util.StringTokenizer;
    
    public class Main {
        public int[][] dp = new int[100002][2];   
        public int[][] tree = new int[100002][300];  //tree[i][3] = num表示第i个节点的第3个孩子节点为第num个节点
        /*
         * 参数point1:表示输入的第point1个节点，不是节点权值
         * 参数point2:表示输入的第point2的节点，不是节点权值
         * 说明：由于题目仅仅给出边的说明，并未说明两个节点谁是父母节点，所以以下有两种情形
         */
        public void creatTree(int point1, int point2) {
            int i = 0;
            //当第point1个节点为父母节点时
            while(tree[point1][i] != 0) i++;  //如果第point1个节点已经有孩子了，再增加一个孩子  
            tree[point1][i] = point2;
            int j = 0;
            //当第point2个节点为父母节点时
            while(tree[point2][j] != 0) j++;
            tree[point2][j] = point1;
        }
        /*
         * 参数satrt:开始对树进行DFS遍历的开始节点，为具体节点位置，不是节点权值
         * 参数root:为第start个节点的直接父母节点位置，root = 0表示根节点的父母节点
         */
        public void dfs(int start, int root) {
            int child = tree[start][0];  //第start个节点的第1个孩子节点
            for(int i = 0;child != 0;i++) {
                child = tree[start][i];
                if(child != root) {  //防止出现start的孩子成为start的父亲情况
                    dfs(child, start);
                    dp[start][1] += dp[child][0];  
                    dp[start][0] += (dp[child][1] > dp[child][0] ? dp[child][1] : dp[child][0]);
                }
            }
        }
        
        public static void main(String[] args) throws IOException {
            Main test = new Main();
            //Scanner in = new Scanner(System.in);
            BufferedReader reader=new BufferedReader(new InputStreamReader(System.in));
            
            String input=reader.readLine();
            int n =	Integer.parseInt(input);
            String input1=reader.readLine();
            StringTokenizer tok0=new StringTokenizer(input1);
            for(int i = 0;i < n;i++) {
                test.dp[i + 1][1] = Integer.valueOf(tok0.nextToken());
            }
            for(int i = 0;i < n - 1;i++) {
            	String input2=reader.readLine();
            	StringTokenizer tok=new StringTokenizer(input2);
                int point1=Integer.valueOf(tok.nextToken());
                int point2=Integer.valueOf(tok.nextToken());
                test.creatTree(point1, point2);
            }
            test.dfs(1, 0);   //从创建的数的根节点（即第1个顶点，0表示根节点的父母节点）开始进行DFS遍历
            int max = (test.dp[1][1] > test.dp[1][0] ? test.dp[1][1] : test.dp[1][0]);
            System.out.println(max);
        }
    }

在网上找到一个AC了的代码，分析一下代码的缺陷在哪，

import java.io.*;
    import java.util.*;
    
    public class Main {
    	
    	final static int MAX_N = 100010;
    
    	PrintWriter out;
    	InputReader cin;
    	int edgecnt;
    	int dp[][] = new int[MAX_N][2];
    	Edge E[] = new Edge[MAX_N * 2];
    	int head[] = new int[MAX_N];
    	int sta[] = new int[MAX_N * 2];
    	boolean vis[] = new boolean[MAX_N];
    	
    	class Edge {
    		int u, v, nxt;
    		Edge () {
    			
    		}
    		Edge (int _u, int _v, int _n) {
    			u = _u;
    			v = _v;
    			nxt = _n;
    		}
    	}
    	class InputReader {
    		InputReader(InputStream in) {
    			reader = new BufferedReader(new InputStreamReader(in));
    			tokenizer = new StringTokenizer("");
    		}
    
    		private String next() throws IOException {
    			while (!tokenizer.hasMoreTokens()) {
    				tokenizer = new StringTokenizer(reader.readLine());
    			}
    			return tokenizer.nextToken();
    		}
    
    		public Integer nextInt() throws IOException {
    			return Integer.parseInt(next());
    		}
    		private BufferedReader reader;
    		private StringTokenizer tokenizer;
    	}
    
    	
    	void add(int u, int v) {
    		E[edgecnt] = new Edge(u, v, head[u]);
    		head[u] = edgecnt++;
    	}
    	
    	void dfs(int x, int fa) {
    		Arrays.fill(vis, false);
    		int top = 0;
    		vis[x] = true;
    		sta[top++] = x;
    		while (top > 0) {
    			int u = sta[top - 1];
    			boolean Ed = false;
    			for (int i = head[u]; i + 1 != 0; i = E[i].nxt) {
    				int v = E[i].v;
    				if (vis[v]) continue;
    				Ed = true;
    				sta[top++] = v;
    				vis[v] = true;
    			}
    			if (Ed) continue;
    			--top;
    			for (int i = head[u]; i + 1 != 0; i = E[i].nxt) {
    				int v = E[i].v;
    				dp[v][0] += Math.max(dp[u][0], dp[u][1]);
    				dp[v][1] += dp[u][0];
    				
    			}
    		}
    	}
    	
    	void run() throws IOException {
    		int n = cin.nextInt();
    		
    		for (int i = 1; i <= n; ++i) 
    			dp[i][1] = cin.nextInt();
    		Arrays.fill(head, -1);
    		for (int i = 1; i < n; ++i) {
    			int u = cin.nextInt();
    			int v = cin.nextInt();
    			add(u, v);
    			add(v, u);
    		}
    		dfs(1, -1);
    		int ans = Math.max(dp[1][0], dp[1][1]);
    		out.println(ans);
    		out.close(); 
    	}
    
    	public static void main(String[] args) throws IOException {
    		new Main().run();
    	}
    
    	Main() {
    		cin = new InputReader(System.in);
    		out = new PrintWriter(System.out);
    	}
    
    }

这是别人写的代码让我们看一下问题。

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

import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStream;
    import java.io.InputStreamReader;
    import java.io.PrintWriter;
    import java.util.StringTokenizer;
    
    public class Main {
        public  int[][] dp = new int[100002][2];   
        public int[][] tree = new int[100002][300];  //tree[i][3] = num表示第i个节点的第3个孩子节点为第num个节点
        PrintWriter out;
        InputReader cin;
        /*
         * 参数point1:表示输入的第point1个节点，不是节点权值
         * 参数point2:表示输入的第point2的节点，不是节点权值
         * 说明：由于题目仅仅给出边的说明，并未说明两个节点谁是父母节点，所以以下有两种情形
         */
        public void creatTree(int point1, int point2) {
            int i = 0;
            //当第point1个节点为父母节点时
            while(tree[point1][i] != 0) i++;  //如果第point1个节点已经有孩子了，再增加一个孩子  
            tree[point1][i] = point2;
            int j = 0;
            //当第point2个节点为父母节点时
            while(tree[point2][j] != 0) j++;
            tree[point2][j] = point1;
        }
        /*
         * 参数satrt:开始对树进行DFS遍历的开始节点，为具体节点位置，不是节点权值
         * 参数root:为第start个节点的直接父母节点位置，root = 0表示根节点的父母节点
         */
        public void dfs(int start, int root) {
            int child = tree[start][0];  //第start个节点的第1个孩子节点
            for(int i = 0;child != 0;i++) {
                child = tree[start][i];
                if(child != root) {  //防止出现start的孩子成为start的父亲情况
                    dfs(child, start);
                    dp[start][1] += dp[child][0];  
                    dp[start][0] += Math.max(dp[child][1], dp[child][0]);
                }
            }
        }
        void run() throws IOException {
        	 int n =	cin.nextInt();
             for(int i = 0;i < n;i++) {
                 dp[i + 1][1] = cin.nextInt();
             }
             for(int i = 0;i < n - 1;i++) {
                 int point1=cin.nextInt();
                 int point2=cin.nextInt();
                 creatTree(point1, point2);
             }
             dfs(1, 0);   //从创建的数的根节点（即第1个顶点，0表示根节点的父母节点）开始进行DFS遍历
             int max = Math.max(dp[1][1], dp[1][0]);
             out.println(max);
             out.close();
    	}
        public static void main(String[] args) throws IOException {
        	new Main().run();
        }
        
        Main() {
    		 cin = new InputReader(System.in);
    		 out = new PrintWriter(System.out);
    	}
    
    	class InputReader {
    		InputReader(InputStream in) {
    			reader = new BufferedReader(new InputStreamReader(in));
    			tokenizer = new StringTokenizer("");
    		}
    
    		private String next() throws IOException {
    			while (!tokenizer.hasMoreTokens()) {
    				tokenizer = new StringTokenizer(reader.readLine());
    			}
    			return tokenizer.nextToken();
    		}
    
    		public Integer nextInt() throws IOException {
    			return Integer.parseInt(next());
    		}
    		private BufferedReader reader;
    		private StringTokenizer tokenizer;
    	}
    }

路过的大神，帮帮忙！