洛谷 P1272/POJ 1947 Rebuilding Roads 题解【树形DP】

点击量：218

    它真的只是树形DP啊。。。

目录

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.]

题意：

给出一棵树，N≤150，问最少切断多少条边会使得图中分离出一块节点数为p的连通块。

题解：

    对于一棵树，f[i][j]表示在i为根的子树中产生j大小的连通块所需切断的最少边数，并且连通块包含i节点。为什么要包含i节点呢？因为如果不包含i，就无法保证连通，当连通块在子树中连通且不包含i时，一定在某个儿子的子树中更新完毕了。为了避免这种情况，我们每做完一棵子树，就更新一次答案。

    那么因为一棵树是基于一个根的，所以连通块的合并可以当背包做。因为根节点也要算一个点，所以每访问到一个点初始化f[x][1]=0。转移和树形背包一样，只不过要注意一点：当这个连通块不转移/不贡献答案时，就意味着把这个连通块切掉，在DP转移时要+1。也就是说，对于每棵子树，DP转移时不是和自己原来的值比较，而是和自己原来的值+1比较。在一般的树形DP中，如果不更新就取自己原来的值，但是在这个题中这样转移是不合法的，但是我们又可能要用到最原始的状态，这样我们就开个g数组用来转移，这样就会无后效性了。

    要注意一点，这里是01背包，所以枚举状态要从大到小。在g数组中转移的f（原DP数组）状态是要+1的，合并时如果发现当前子树取0，也是要+1的，也就相当于把这棵子树切掉了。

    因此这个题的全部操作都被压在了状态转移方程里，除了注意割掉边的情况以外，就是一个树形背包了。g数组每次要记得置∞。

Code：

#include<cstdio>
#include<cstring>
int min(int x,int y)
{
    return x<y?x:y;
}
struct edge
{
    int n,nxt;
    edge(int n,int nxt)
    {
        this->n=n;
        this->nxt=nxt;
    }
    edge()
    {
        nxt=-1;
    }
}e[400];
int head[200],ecnt=-1;
void add(int from,int to)
{
    e[++ecnt]=edge(to,head[from]);
    head[from]=ecnt;
    e[++ecnt]=edge(from,head[to]);
    head[to]=ecnt;
}
int f[200][200];
int w[200],m;
int ans=500;

void dfs(int x)
{
    int g[200];
    memset(g,0x3f,sizeof(g));
    f[x][1]=0;

    w[x]=1;
    for(int i=head[x];~i;i=e[i].nxt)
    {
        if(f[e[i].n][1]==0x3f3f3f3f)
        {
            memset(g,0x3f,sizeof(g));
            dfs(e[i].n);
            w[x]+=w[e[i].n];
            for(int j=w[e[i].n];j>=0;j--)//新增
                for(int k=w[x];k>=j;k--)//原来
                    g[k]=min(g[k],min(f[x][k]+1,f[x][k-j]+f[e[i].n][j]+(j==0)));
            for(int i=1;i<=w[x];i++)
                f[x][i]=g[i];
            f[x][1]++;
        }
    }
    for(int i=1;i<=w[x];i++)
        f[x][i]=g[i];
    f[x][0]=0;
    //f[x][0]=1;
    f[x][w[x]]=0;
    ans=min(ans,f[x][m]+1);
}
int main()
{
    int n,u,v;
    scanf("%d%d",&n,&m);
    memset(head,-1,sizeof(head));
    memset(f,0x3f,sizeof(f));
    for(int i=1;i<n;i++)
    {
        scanf("%d%d",&u,&v);
        add(u,v);
    }
    dfs(1);
    //f[1][n]=0;
    ans=min(ans,f[1][m]);
    printf("%d\n",ans);
    return 0;
}