# 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 阅读(1136) 评论(0)  编辑 收藏 引用

 只有注册用户登录后才能发表评论。 【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库