摘取最多苹果数&&DP

某企业校招的编程题目，问题大致描述如下：

有一棵树有N个节点，其中有K个节点有苹果。在每条边至多走一次的情况下，最多可以摘到的苹果数。其中，可以从任意一个节点出发。

---

---

---

---

---

代码如下：

import java.util.*; public class Main { public static void main(String[] args) { Solution s=new Solution(); // int a[]={2,3,4}; // int b[][]={{1,2},{1,3},{1,4}}; int a[]={2,3,5,6}; int b[][]={{1,2},{1,3},{2,5},{2,4},{3,6},{3,7},{6,8}}; int res = s.collectApples(8, 4,a ,b); System.out.println(res); } } class Node{ private boolean at;//是否访问过 private int num;//节点值 private boolean apple;//是否有苹果 //保存关联节点 List<Node> childs=new ArrayList<Node>(); public Node(Node p, boolean a,int num){ this.apple=a; this.num=num; } public void add(Node node){ this.childs.add(node); } public boolean isAccess(){ return this.at; } public boolean existApple(){ return this.apple; } public void noAccess(){ this.at=false; } public void access(){ this.at=true; } //打印时的合理输出 public String toString(){ return String.valueOf(num); } //测试节点内部构造的关联节点是否正确 public void printChilds(){ for (int i = 0; i < childs.size(); i++) { System.out.print(childs.get(i)+","); } System.out.println(); } } class Solution { int collectApples(int N, int K, int[] applesAtNodes, int[][] connectedNodes) { Map<Integer, Node> map=new HashMap<Integer, Node>(); //首先实例化有苹果的节点 for(int i=0;i<K;i++){ int cur = applesAtNodes[i]; Node node=new Node(null,true,cur); map.put(cur,node); } int m=connectedNodes.length; // System.out.print(map); //根据是否有边，构造图结构 for(int i=0;i<m;i++){ int pNum=connectedNodes[i][0]; int cNum=connectedNodes[i][1]; Node pn; Node cn; if(map.containsKey(pNum)){ pn=map.get(pNum); }else{ pn=new Node(null,false,pNum); map.put(pNum, pn); } if(map.containsKey(cNum)){ cn=map.get(cNum); }else{ cn=new Node(pn,false,cNum); map.put(cNum, cn); } //通过任何一方找到另一方，必须各自拥有对方 pn.add(cn); cn.add(pn); } int max=-1; //System.out.println(map);//打印构造的map for(Node node:map.values()){ //测试构造的图结构是否正确 // System.out.println("node:"+node); // node.printChilds(); //重新一轮之前，重置所有节点未遍历过 resetNoAccess(map); int num1=search(node);//计算以从节点出发的摘取的最大苹果树 // System.out.println("num1:"+num1+",max:"+max); max=Math.max(max,num1); } return max; } //重置map中节点的是否访问属性 void resetNoAccess(Map<Integer, Node> map){ for(Node node:map.values()){ node.noAccess(); } } //以某个节点出发递归，计算最大可摘取苹果树 int search(Node node){ if(node==null || node.isAccess())return 0; node.access(); //深度遍历未访问的关联节点 int num2=0; for(int i=0;i<node.childs.size();i++){ int cur=search(node.childs.get(i)); num2=Math.max(cur,num2); } if(node.existApple())return 1 + num2;//有苹果的情况 else return num2; } }