poj1947(Rebuilding Roads 树中独立出m个点 最少切割的边数 树形背包dp)

题目

题意： 在n个结点n-1条边的树中取m个点所需要的最少切割的边数。

思路： dp[x][j]：以x为根的子树中，取m个点 包括x 所需要最少切割的边数。这个留下的m个点显然是联通的。

注意这个dp[x][j]的定义。

#include<cstdio>
#include<iostream>
#include<cstring>
#define m(a,b) memset(a,b,sizeof a)
using namespace std;
typedef long long ll;
const int N=150+5,INF=0x3f3f3f3f;
struct Edge{int to,nex;}edge[N<<1];int head[N],tot;
inline void add(int from,int to){
    edge[++tot]=(Edge){to,head[from]},head[from]=tot;
    edge[++tot]=(Edge){from,head[to]},head[to]=tot;
}
int in[N],dp[N][N],n,m;
void dfs(int x,int fa){
    dp[x][1]=0;//看21行代码 就知道这一行初始化的道理啦
    for(int i=head[x];i;i=edge[i].nex){
        int y=edge[i].to;
        if(y==fa) continue;
        dfs(y,x);
        for(int j=m;j>=1;--j){
            dp[x][j]=dp[x][j]+1;//y这颗子树一个都不入选
            for(int k=1;k<j;++k){//y这颗子树入选k个
                dp[x][j]=min(dp[x][j],dp[y][k]+dp[x][j-k]);
            }
        }
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1,x,y;i<n;++i) scanf("%d%d",&x,&y),add(x,y),++in[y];
    m(dp,INF);
    if(n==1) {printf("0\n");return 0;}
    int root;
    for(int i=1;i<=n;++i) if(!in[i]) {root=i;break;}//叶子节点作为根节点 没有父亲
    dfs(root,root);
    int ans=dp[root][m];
    for(int i=1;i<=n;++i) ans=min(ans,dp[i][m]+1);
    printf("%d\n",ans);
}