注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

OI之路,漫漫人生

只为梦想,没有理由

 
 
 

日志

 
 

POJ1947Rebuilding Roads题解  

2014-03-10 20:44:35|  分类: POJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
                                                                      重建道路
                                                  BY   LGS
题目大意:一棵树中,求删除最少的边分离出给定P个结点的子树。

题解:此题是赤裸裸的树形DP,对于树形DP,只需要递归做下DP即可。某个点,可以由下面的点推过来,设F[I][J]表示i结点,分离出J个结点的子树所需要最少的边数,我们可以保证这个决策能全局最优。而对于每个i点,它的一个儿子K点,只有两种情况,1.把K割掉,那么如果枚举生成P个结点的子树,直接F[I][P]+1;2.把K留下,那么如果枚举生成P个结点的子树,可以由min(F[K][P-J]+F[I][J]) (1<=J<P);最终的F[I][P]就是两种情况的最优值。具体看下面代码的注释。

总结:树形DP做较水,貌似也可以用多维背包,但我不会。。。
代码:
#include<cstdio>
#define maxn 99999999
using namespace std;
int i,j,x,y,n,ans,m;
bool q[200];
int f[200][200],dp[200][200];
int min(int a,int b){return (a>b)?b:a;}
void dfs(int w)
 {
 for (int i=0;i<=m;i++)
         dp[w][i]=maxn;
 dp[w][1]=0;//初始化
 for (int i=1;i<=f[w][0];i++)//枚举儿子结点
     {
     dfs(f[w][i]);//先递归做完儿子DP。
     for (int j=m;j>=1;j--){//顺序千万不能反,否则下面+DP[W][K]会重复累加。
          int tem=dp[w][j]+1;
       for (int k=1;k<j;k++)
               tem=min(tem,dp[f[w][i]][j-k]+dp[w][k]);//状态更新。
                  dp[w][j]=tem;
                          }
     }
 }
int main()
{
 scanf("%d%d",&n,&m);
 for (i=2;i<=n;i++)
    {
    scanf("%d%d",&x,&y);
    f[x][0]++;f[x][f[x][0]]=y;
    q[y]=true;
    }//用邻接表存,提高递归速度;(好像这个不叫领接表)
for (i=1;i<=n;i++)
  if (!q[i]) break;//其中没有父亲的结点为根结点
int root=i;
dfs(root);
ans=dp[root][m];
for (i=1;i<=n;i++)
        if (i!=root)
      ans=min(ans,dp[i][m]+1);//除了根结点外,其它必定有父亲,答案需要再加个割断与父亲的连接。
printf("%d",ans);
//for(;;);
return 0;
}

  评论这张
 
阅读(6)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018