重建道路 树形DP

时间：2022-10-27 21:17:09

重建道路 树形DP

给一棵树，问最少断多少边使得这棵树树最终只有\(p​\)个节点

设计dp状态\(f[u][i][j]\)表示节点\(u\)，到第\(i\)个儿子，使\(j\)个节点分离，但是不分离\(u\)最少需要断的边数。类比背包，容易得到转移方程：

\[f[u][i][j]=min{f[u][i-1][j-k]+f[v][n][k]}
\]

再优化一维\(i\)，状态变为\(f[u][j]\)，此时必须倒序遍历\(j\)。

需要注意的是，最后答案并不是\(f[1][sz[1]-p]\)，因为最后可能把节点1也删了，所以必须在每个满足子树节点数\(\ge p\)的节点处统计一下答案。

\[ans=min(f[u][sz[u]-p]+f[u][sz[u]], ans)
\]

其中注意\(f[1][sz[1]]=0\)，因为不需要将树根与其父亲分离（它没父亲）

#include <cstdio>

#include <cstring>

#define MAXN 155

#define MIN(A,B) ((A)<(B)?(A):(B))

using namespace std;

int n,p,ans;

int head[MAXN],nxt[MAXN*2],vv[MAXN*2],tot;

inline void add_edge(int u, int v){

    vv[++tot]=v;

    nxt[tot]=head[u];

    head[u]=tot;

}

int f[MAXN][MAXN],sz[MAXN];

void load(int u, int fa){

    sz[u]=1;

    f[u][0]=0;

    for(int i=head[u];i;i=nxt[i]){

        int v=vv[i];

        if(v==fa) continue;

        load(v, u);

        sz[u]+=sz[v];

    }

    f[u][sz[u]]=1;

}

void dfs(int u, int fa){

    for(int i=head[u];i;i=nxt[i]){

        int v=vv[i];

        if(v==fa) continue;

        dfs(v, u);

        for(int j=sz[u];j>=0;--j)

            for(int k=0;k<=MIN(sz[v], j);++k){

                f[u][j]=MIN(f[v][k]+f[u][j-k], f[u][j]);

            }

    }

    if(sz[u]>=p) ans=MIN(f[u][sz[u]-p]+f[u][sz[u]], ans);

}

int main(){

    scanf("%d %d", &n, &p);

    for(int i=2;i<=n;++i){

        int u,v;

        scanf("%d %d", &u, &v);

        add_edge(u, v);

        add_edge(v, u);

    }

    memset(f, 0x3f, sizeof(f));

    ans=0x3f3f3f3f;

    load(1, 0);

    f[1][sz[1]]=0;

    dfs(1, 0);

    printf("%d", ans);

    return 0;

}

/*

f[u][i][j]=min{f[u][i-1][j-k]+f[v][n][k]}

*/

相关文章