POJ 1947 나무 가방

제목: 나무 한 그루를 몇 부분으로 분해하고 그 중 한 부분은 p로 한다. 상술한 조작을 실현하려면 최소한 몇 개의 변을 삭제해야 한다.
방법: 나무 배낭 입니다.뿌리 노드를 확립하고 각 노드의 자손 수를 찾아내다.이 문제를 푸는 것은 각 하위 트리를 하나의 상태로 확립하고 상태 방정식을 구축하는 것이다. dp[u][j]=min(dp[u][j-k]+dp[v][k])이다. 그 중에서 jk는 각각 u, v가 삭제하고자 하는 노드를 대표하는데 u를 뿌리로 하는 나무에서 j개의 노드를 삭제하는 데 필요한 변수의 수를 구하는 것이다.여기 dp[u][son[u]=0, 이 산식은 u가 부 노드가 있을 때만 성립된다. 그의 부 노드로 구성된 나무는son[u]개를 삭제해야 한다.
노드는 u와 연결된 가장자리만 삭제할 수 있습니다.또 하나의 문제는 최종적으로 답안을 생성할 때 각 노드를 두루 훑어보아야 하며 전체 조상 노드를 제외하고 자수를 독립적으로 형성하기 위해 다른 노드의 dp값은 반드시 1을 더해야 한다는 것이다.

#include<stdio.h>
#include<string.h>
#define eps 1e8
#define LMT 155
/*    ，       */
typedef struct
{
    int u,v,next;
}line;
line e[LMT<<1];
int dp[LMT][LMT],next[LMT],son[LMT];
int all,p,n;
inline int min(int a,int b)
{
    return a<b?a:b;
}
void insert(int u,int v)
{
    e[all].u=u;
    e[all].v=v;
    e[all].next=next[u];
    next[u]=all++;
    e[all].u=v;
    e[all].v=u;
    e[all].next=next[v];
    next[v]=all++;
}
void inidfs(int u,int pre)
{
    son[u]=1;
    int v,x;
    for(x=next[u];x!=-1;x=e[x].next)
    if(e[x].v!=pre)
    {
        v=e[x].v;
        inidfs(v,u);
        son[u]+=son[v];
    }
    dp[u][son[u]]=1;
    dp[u][0]=0;
}
void dfs(int u,int pre)
{
    int x,v,j,k;
    for(x=next[u];x!=-1;x=e[x].next)
    if(e[x].v!=pre)
    {
        v=e[x].v;
        dfs(v,u);
        for(j=son[u]-1;j>=0;j--)
          for(k=0;k<=son[v]&&k<=j;k++)
          if(dp[u][j-k]!=eps)
            dp[u][j]=min(dp[u][j],dp[u][j-k]+dp[v][k]);
    }
}
int main()
{
    int i,ans,j;
    while(scanf("%d%d",&n,&p)!=EOF)
    {
        memset(next,-1,sizeof(next));
        memset(son,0,sizeof(son));
        all=0;
        for(i=1;i<n;i++)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            insert(u,v);
        }
        for(i=1;i<=n;i++)
         for(j=0;j<=n;j++)
         dp[i][j]=eps;
         inidfs(1,0);
         dfs(1,0);
         ans=dp[1][son[1]-p];
         for(i=2;i<=n;i++)
         if(son[i]>=p)
         ans=min(ans,dp[i][son[i]-p]+1);
         printf("%d
",ans);
    }
    return 0;
}