洛谷 P2015 二叉苹果树

小咪咪 2023-07-19 04:58 24阅读 0赞

## 题目描述 ##

有一棵苹果树，如果树枝有分叉，一定是分2叉（就是说没有只有1个儿子的结点）

这棵树共有N个结点（叶子点或者树枝分叉点），编号为1-N,树根编号一定是1。

我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。下面是一颗有4个树枝的树

2   5
     \ / 
      3   4
       \ /
        1

现在这颗树枝条太多了，需要剪枝。但是一些树枝上长有苹果。

给定需要保留的树枝数量，求出最多能留住多少苹果。

## 输入格式 ##

第1行2个数，N和Q(1<=Q<= N,1<N<=100)。

N表示树的结点数，Q表示要保留的树枝数量。接下来N-1行描述树枝的信息。

每行3个整数，前两个是它连接的结点的编号。第3个数是这根树枝上苹果的数量。

每根树枝上的苹果不超过30000个。

## 输出格式 ##

一个数，最多能留住的苹果的数量。

## 输入输出样例 ##

**输入 \#1**

5 2
    1 3 1
    1 4 10
    2 3 20
    3 5 20

**输出 \#1**

方法一：

树形动态规划

#include<iostream>
    #include<algorithm>
    #include<string>
    #include<vector>
    #include<map>
    using namespace std;
    const int MAXN = 102; 
    const int INF = 999999;
    
    struct Node{
    	int v;
    	int w;
    	Node(int v,int w){
    		this->v = v;
    		this->w = w;
    	}
    }; 
    vector<Node> adj[MAXN];
    bool vis[MAXN];
    int dp[MAXN][MAXN]; //dp[u][m]=k表示以u为根节点的子树被分配m条保留边时，最多能留住k个苹果 
    vector<Node> son[MAXN];
    
    void DFS(int u,int n,int q){
    	vis[u] = true;
    	for(int i=0;i<adj[u].size();i++){
    		int v = adj[u][i].v;
    		int w = adj[u][i].w;
    		if(!vis[v]){
    			DFS(v,n,q);
    			son[u].push_back(Node(v,w));
    		}
    	}
    	if(son[u].size() > 0){
    		for(int i=1;i<=q;i++){ //当前节点被分配的保留边的边数 
    			for(int j=0;j<=i;j++){  //分配给左儿子j个保留边 
    				int left = son[u][0].v;
    				int right = son[u][1].v;
    				int lw = son[u][0].w;
    				int rw = son[u][1].w;
    				
    				int temp = 0;
    				if(j > 0){  //如果分配给左儿子的保留边 >1 
    					temp += dp[left][j-1] + lw;  
    				}
    				if(i-j > 0){ //如果分配给右儿子的保留边 >1 
    					temp += dp[right][i-j-1] + rw; 
    				}
    				dp[u][i] = max(dp[u][i],temp);
    			}
    		}	
    	}	
    }
    
    int main(){
    	int n,q;
    	int u,v,w;
    	cin>>n>>q;
    	for(int i=1;i<n;i++){
    		cin>>u>>v>>w;
    		adj[u].push_back(Node(v,w));
    		adj[v].push_back(Node(u,w));
    	}
    	DFS(1,n,q);
    	cout<<dp[1][q]<<endl;
    	return 0;
    }

方法二：

树形动态规划+01背包思想

#include<iostream>
    #include<algorithm>
    #include<string>
    #include<vector>
    #include<map>
    using namespace std;
    const int MAXN = 102; 
    const int INF = 999999;
    
    struct Node{
    	int v;
    	int w;
    	Node(int v,int w){
    		this->v = v;
    		this->w = w;
    	}
    }; 
    vector<Node> adj[MAXN];
    bool vis[MAXN];
    int dp[MAXN][MAXN]; 
    /*
    **dp[i][j]表示以i为根节点的子树当拥有j条保留边时，
    **所能保住的最多苹果树。 
    */ 
    
    void DFS(int u,int n,int q){
    	vis[u] = true;
    	/*
    	** 首先，我们需要知道，01背包需要两层for循环
    	** 外层for循环用来遍历物品
    	** 内层for循环用来遍历背包的容量。 
    	*/ 
    	/*
    	**这个for循环就类似01背包中的外层for循环
    	**现在的子节点就类似物品
    	**我们把给某个物品的容量
    	**改成给某个子节点的保留边。 
    	**（这里的子节点指的是以它为根的子树） 
    	*/
    	for(int i=0;i<adj[u].size();i++){
    		int v = adj[u][i].v;
    		int w = adj[u][i].w;
    		if(!vis[v]){
    			DFS(v,n,q);
    			//这个for循环类似01背包中的内层for循环，相当于是背包的容量 
    			//在这里表示的是以U为根的子树的保留边数量 
    			//请看下面标有@1234 的那句话，所以我们要从q循环到0，而不是从0循环到q 
    			for(int j=q;j>=0;j--){
    				//分配给这个子节点K个保留边，类似背包花费一定的容量放一件物品。
    				//因为是01背包，放入的物品不可以继续放入
    				//@1234：类似的，给这个节点分配了K个保留边之后，剩下的保留边不会再分配给这个子节点 
    				for(int k=0;k<j;k++){  
    					dp[u][j] = max(dp[u][j],dp[v][k]+dp[u][j-k-1]+w); 
    				}
    			}
    		}
    	}
    }
    
    int main(){
    	int n,q;
    	int u,v,w;
    	cin>>n>>q;
    	for(int i=1;i<n;i++){
    		cin>>u>>v>>w;
    		adj[u].push_back(Node(v,w));
    		adj[v].push_back(Node(u,w));
    	}
    	DFS(1,n,q);
    	cout<<dp[1][q]<<endl;
    	return 0;
    }