真的是假的吗?

题解 P1272 【重建道路】
题解
//树形DP
//大致思路:
//递归操作,f[i][j]表示保留i为根的子节点。
//c数组记录点的度。
//因为这是一棵树,所以每个点的度为1
//然后随便设一个根,我设的1为根,1的根就为0.
//递归时传入两个参数,为当前节点和当前节点的根。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

define LL 153

int hea[LL],num,n,p,a,b,c[LL],f[LL][LL],r[LL];
int ans=0x3f3f3f3f;
struct edge{
    int nex,to;
}edge[LL<<1];
void add_edge(int from,int to)
{
    edge[++num].nex=hea[from];
    edge[num].to=to;
    hea[from]=num;
}
void dfs(int u,int root)
{
    int i,j,k;
    f[u][1]=c[u];//只选这个根自己需要切掉几条边。。
    for(i=hea[u];i;i=edge[i].nex)
    if(edge[i].to!=root)//如果是根就不要搜了
    {
        dfs(edge[i].to,u);
        for(j=p;j>=1;j--)
          for(k=1;k<j;k++)
            f[u][j]=min(f[u][j],f[u][k]+f[edge[i].to][j-k]-2);// emmm,至于为什么-2.。个人认为本题最坑的一点,害的我想了好久,一定是我太菜了,因为在初始化的时候已经把所有与u和edge[i].to相连接的节点给砍掉了,但是u和edge[i].to相连的的度应该保留,而这段相连的度,在u中加了一次,在edge[i].to中也加了一次,所以应该-2。
    }
}
int main()
{
    int i,j;
    scanf("%d%d",&n,&p);
    for(i=1;i<n;i++)
    {
        scanf("%d%d",&a,&b);
        c[a]++,c[b]++;//记录a,b的度。
        add_edge(a,b),add_edge(b,a);//建双向边,因为1也不是这棵树的真根,只是因为方便设的。
    }
    memset(f,0x3f,sizeof(f));
    dfs(1,0);
    for(i=1;i<=n;i++) ans=min(f[i][p],ans);
    printf("%d\n",ans);
    return 0;
}
评论