POJ 1947 Rebuilding Roads (樹形dp 經典題)

 

Rebuilding Roads Time Limit: 1000MS   Memory Limit: 30000K Total Submissions: 9499   Accepted: 4317

 

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

 

題目鏈接：http://poj.org/problem?id=1947

 

題目大意：一顆含有n個結點的樹，求減去最少的邊使得該樹只含有p個結點

 

題目分析：典型的樹形dp，在樹上進行動態規劃，設dp[s][i]表示以s為根的子樹含有i個結點需要刪去的邊數，則得到轉移方程：

對於i的子樹k:

1.不加子樹k，dp[s][i] = dp[s][i] + 1 （不加子樹k，相當於刪去一條邊）

2.加子樹k，dp[s][i] = min(dp[s][j] ＋ dp[k][i - j]) (1<= j <= i) (以s為根的樹的結點數加上其子樹的結點數等於i)

最後答案就是在dp[i][m]中取小，要注意的一點是，如果i不是根，值還需要＋1，因為要脫離原來的根，還要去掉一條邊

這裡需要注意，dp過程是自下而上的，也就是從葉子到根，而不是從根到葉子

 

 

#include 
#include 
#include 
using namespace std;
int const INF = 0x3fffffff;
int const MAX = 155;

struct Edge
{
    int to, next;
}e[MAX * MAX / 2];

int n, m;
int head[MAX], cnt, root;
int fa[MAX], dp[MAX][MAX];

void Add(int x, int y)  //加邊
{
    e[cnt].to = y;
    e[cnt].next = head[x];
    head[x] = cnt++;
}

void DFS(int u)
{
    for(int i = 0; i <= m; i++) //初始化為無窮大
        dp[u][i] = INF;               
    dp[u][1] = 0;               //根結點本就一個點，不需要減邊
    for(int i = head[u]; i != -1; i = e[i].next)  //同層
    {
        int v = e[i].to;    //u的子樹
        DFS(v);
        for(int j = m; j >= 1; j--) 
        {
            for(int k = 0; k < j; k++)
            {
                if(k)   //不加子樹k
                    dp[u][j] = min(dp[u][j], dp[u][j - k] + dp[v][k]);
                else    //加上子樹k
                    dp[u][j] = dp[u][j] + 1;
            }
        }
    }
}

int main()
{
    scanf("%d %d", &n, &m);
    cnt = 0;
    memset(fa, -1, sizeof(fa));
    memset(head, -1, sizeof(head));
    for(int i = 1; i < n; i++)
    {
        int x, y;
        scanf("%d %d", &x, &y);
        Add(x, y);
        fa[y] = x;
    }
    for(root = 1; fa[root] != -1; root = fa[root]);
    DFS(root);
    int ans = dp[root][m];
    for(int i = 1; i <= n; i++)     //除了根節點，其他節點要想成為獨立的根，必先與父節點斷絕關系，所以要先加1
        ans = min(ans, dp[i][m] + 1);
    printf("%d\n",ans);    
}