poj1947 Rebuilding Roads - 树上背包-删除最少边得到一个大小为p的连通块

635 浏览 0 回复 2020-02-28

工大最菜

+关注

题目链接：http://poj.org/problem?id=1947
题目大意：一棵节点数为n的树。让你删除最少的边。得到一个大小为p的子树。 p<=n<150。

$我们考虑用 f [u] [s] 为选择 u 节点及其子树大小为 s 的删除最小边树$

$d f s 过程中增加一棵子树那么之前的 f [u] [i] 都必须 + 1. 因为必须删除这棵子树$

$然后我们枚举 i ， j 。 j 为这棵子树保留的节点树 f [u] [i] = m a x (f [u] [i], f [t o] [j] + f [u] [i - j]$

$最后统计结果时。取 f [u] [i] ： u 不为根节点时要 + 1 。删除父边。$

#include <math.h>
#include <vector>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#define LL long long
using namespace std;

vector<int> v[205];
int f[205][205];
int n, p;
void dfs(int u, int fa){

    f[u][1]=0;
    for(int i=0; i<v[u].size(); i++){
        int to=v[u][i];
        if(to!=fa){
            dfs(to, u);
            for(int j=p; j>=1; j--){
                f[u][j]+=1;//删除这棵子树
                for(int k=1; k<j; k++){
                    f[u][j]=min(f[u][j], f[to][k]+f[u][j-k]);
                }
            }
        }
    }
}

int main(){
    int a, b;
    scanf("%d%d", &n, &p);
    for(int i=1; i<n; i++){
        scanf("%d%d", &a, &b);
        v[a].push_back(b);
        v[b].push_back(a);
    }
    memset(f, 7, sizeof(f));
    dfs(1, 0);
    int ans=f[1][p];
    for(int i=2; i<=n; i++){
        ans=min(ans, f[i][p]+1);//删除父边
    }

    printf("%d\n", ans);

    return 0;
}