The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

POJ 1947 Rebuilding Roads 第一个树形DP

After solving this problem,I can't help admitting that DP is a world which fully fill with amazement,from the simple one dimension DP,to two dimension DP even to staue DP,tree DP,DP problem is just like a kaleidoscope. But the further reflection reveal that it is always the same because of the similar essence.in my eyes,every DP problem has a (mostly two dimension)table and a equation bewteen two states.If we can controll the table and the relationship between every states,we can conque the problem completely.
The following is my code ,according to the big fish foreverlin.
 
#include<iostream>
#include
<cmath>
#include
<algorithm>
#include
<vector>
using namespace std;
#define INF 999999999
#define MAX 151
vector
<int> hash[MAX];
int dp[MAX][MAX];
int n,p;

void dfs(int x)//x代表当前访问结点
{
    
int i,j,k;
    
int len=hash[x].size();
    
for(i=0;i<len;i++)
        dfs(hash[x][i]);
    
//////////////////////////////////////////////////////////////////////////
    //后序遍历,从叶子往上逐层递推
    if(x==1)    dp[x][1]=hash[x].size();
    
else dp[x][1]=hash[x].size()+1;
    
for(k=0;k<len;k++)
    
{
        
for(i=p-1;i>=1;i--)
        
{
            
if(dp[x][i]!=INF)
            
{
                
for(j=1;i+j<=p;j++)
                
{
                    
if(dp[hash[x][k]][j]!=INF)
                        dp[x][i
+j]=min(dp[x][i+j],dp[x][i]+dp[hash[x][k]][j]-2);
                }

            }

        }

    }

}




int main()
{
    scanf(
"%d%d",&n,&p);
    
int i,j;
    
int t1,t2;
    
for(i=1;i<=n-1;i++)
    
{
        scanf(
"%d%d",&t1,&t2);
        hash[t1].push_back(t2);
    }

    
for(i=1;i<=n;i++)
        
for(j=1;j<=p;j++)
            dp[i][j]
=INF;
    dfs(
1);
    
int ans=INF;
    
for(i=1;i<=n;i++)
    
{
        
if(dp[i][p]<ans)
            ans
=dp[i][p];
    }

    printf(
"%d\n",ans);
    
return 0;
    
    


}

posted on 2010-03-07 23:36 abilitytao 阅读(1114) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理