poj1208，POJ-2152 Fire （樹形DP）

題目大意：在一棵樹中選出一些點，選每個點的代價為w(i)，并且對于點 i ，在距離它lim(i)之內必須選一個點，使它作為 i 的依賴點。求最小代價。

題目分析：定義狀態dp(u,k)表示使u為根節點的子樹滿足題意并且節點u依賴節點k產生的最小代價，定義best(u)表示子樹u滿足題意得最小代價。則狀態轉移方程為：

dp(u,k)=w(k)+∑min(dp(v,k)-w(k),best(v))　　dist(u,k)<=lim(u)

　　　　　　　　　　　　　　　dp(u,k)=oo　　dist(u,k)>lim(u)

poj1208，best(u)=min(dp(u,v))　　

其中v為u的子節點。

?

代碼如下：

# include<iostream>
# include<cstdio>
# include<cstring>
# include<vector>
# include<queue>
# include<list>
# include<set>
# include<map>
# include<string>
# include<cmath>
# include<cstdlib>
# include<algorithm>
using namespace std;
# define LL long longconst int N=1005;
const int INF=1000000000;struct Edge
{int to,nxt,w;
};
int cnt,n;
int head[N];
int dp[N][N];
int best[N];
int dis[N][N];
int w[N],lim[N];
Edge e[N<<1];void init()
{cnt=0;memset(head,-1,sizeof(head));for(int i=1;i<=n;++i){best[i]=INF;for(int j=1;j<=n;++j)dp[i][j]=INF;}
}void add(int u,int v,int w)
{e[cnt].to=v;e[cnt].w=w;e[cnt].nxt=head[u];head[u]=cnt++;
}void read()
{scanf("%d",&n);init();for(int i=1;i<=n;++i)scanf("%d",w+i);for(int i=1;i<=n;++i)scanf("%d",lim+i);int a,b,c;for(int i=1;i<n;++i){scanf("%d%d%d",&a,&b,&c);add(a,b,c);add(b,a,c);}
}void getDis(int s,int u,int fa,int d)
{dis[s][u]=d;for(int i=head[u];i!=-1;i=e[i].nxt){int v=e[i].to;if(v==fa) continue;getDis(s,v,u,d+e[i].w);}
}void dfs(int u,int fa)
{for(int i=head[u];i!=-1;i=e[i].nxt){int v=e[i].to;if(v==fa) continue;dfs(v,u);}for(int i=1;i<=n;++i){if(lim[u]<dis[u][i]) continue;dp[u][i]=w[i];for(int j=head[u];j!=-1;j=e[j].nxt){int v=e[j].to;if(v==fa) continue;dp[u][i]+=min(dp[v][i]-w[i],best[v]);}best[u]=min(best[u],dp[u][i]);}
}void solve()
{for(int i=1;i<=n;++i)getDis(i,i,-1,0);	///找出任意兩點之間的距離；dfs(1,-1);printf("%d\n",best[1]);
}int main()
{int T;scanf("%d",&T);while(T--){read();solve();}return 0;
}