(树形DP+背包)POJ1947Rebuilding Roads

Rebuilding Roads

Description

The cows have reconstructed Farmer John's farm, with its N barns (1 <= N <= 150, number 1..N) after the terrible earthquake last May. The cows didn't have time to rebuild any extra roads, so now there is exactly one way to get from any given barn to any other barn. Thus, the farm transportation system can be represented as a tree. 

Farmer John wants to know how much damage another earthquake could do. He wants to know the minimum number of roads whose destruction would isolate a subtree of exactly P (1 <= P <= N) barns from the rest of the barns.

Input

* Line 1: Two integers, N and P 

* Lines 2..N: N-1 lines, each with two integers I and J. Node I is node J's parent in the tree of roads. 

Output

A single line containing the integer that is the minimum number of roads that need to be destroyed for a subtree of P nodes to be isolated. 

Sample Input

11 6

1 2

1 3

1 4

1 5

2 6

2 7

2 8

4 9

4 10

4 11

Sample Output

2

Hint

[A subtree with nodes (1, 2, 3, 6, 7, 8) will become isolated if roads 1-4 and 1-5 are destroyed.] 

Source

​​USACO 2002 February​​

代码实现：

题意：

将一棵n个节点的有根树，删掉一些边变成恰有m个节点的新树。求最少需要去掉几条边。

分析：

定义状态dp(root,k)表示在以root为根节点的子树中，删掉一些边变成恰有k个节点的新树需要删去的最少边数。

对于根节点root的某个儿子son，

要么将son及其所有的子节点全部删掉，则dp(root,k)=dp(root,k)+1，只需删除root与son之间的边；

要么在son的子树中选出一些边删掉，构造出有j个节点的子树，状态转移方程为dp(root,k)=max(dp(root,k),dp(son,j)+dp(root,k-j))。

算法分析：

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <stack>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std;
const int N=310;
struct node
{
    int v;///终端点
    int next;///下一条同样起点的边号
    int w;///权值
}edge[N*2];///无向边，2倍
int head[N];///head[u]=i表示以u为起点的所有边中的第一条边是 i号边
int tot;  ///总边数
int minn;
void add(int u,int v)
{
    edge[tot].v=v;
    //edge[tot].w=w;
    edge[tot].next=head[u];
    head[u]=tot++;
}
int n,m;
int dp[N][N],fa[N],num[N];
void dfs(int u,int fa) 
{
     num[u]=1;///记录u的子节点数量
    for(int i = 0; i <= m; i++) ///初始化为无穷大
      dp[u][i] = 1e18;
    
     dp[u][0]=0;
    for(int i=head[u];i!=-1;i=edge[i].next)
     {
        int v=edge[i].v;
        if(fa==v) continue;   ///如果下一个相邻节点就是父节点，则证明到底层了，开始递归父节点的兄弟节点
        
        dfs(v,u);
        num[u]+=num[v];
        for(int j=min(num[u],m);j>=1;j--)
            for(int k=0;k<(num[v],j);k++)
        {
            if(k!=0)
            dp[u][j]=min(dp[u][j],dp[u][j-k]+dp[v][k]);
            else
                dp[u][j]=dp[u][j]+1;
        }
     }
 
}
int main()
{
    while(~scanf("%d%d",&n,&m))
    {

    memset(head,-1,sizeof(head));
    //memset(dp,0x3f,sizeof(dp));
    memset(fa,-1,sizeof(fa));
    tot=0;
    
    for(int i=1;i<n;i++)
    {
        int u,v;
        num[i]=1;
        scanf("%d%d",&u,&v);
        add(u,v);
        fa[v]=u;
        
    }
    int root=1;
    for(root=1;fa[root]!=-1;root=fa[root]);//寻找根节点
    
    dfs(root,-1);
    int ans = dp[root][m];   
    for(int i = 1; i <= n; i++)   ///除了根节点，其他节点要想成为独立的根，必先与父节点断绝关系，所以要先加1  
    ans = min(ans, dp[i][m] + 1);  
    printf("%d\n",ans);

    }
    
    return 0;
}