POJ 2152 经典树形dp 一张一弛,解题之道陈启峰 具体证明点上面的链接，最后一个例题就是题意也在里面；
题意：给定n个节点组成的树，树有边权.现在要在一些点上建立消防站，每个点建站都有个cost[i]，如果不在当前的点上建站，也要依赖其他的消防站，并且距离不超过limit[i]。求符合上述条件的最小费用建站方案。n <= 1000. best[i]代表以i为根的子树满足条件的最优解； dp[i][j]代表 在i点选择j点为i点的负责点； dis[i][j]代表i到j的距离； 当dis[i][j]<=limit[i]时还可以分成这么几个阶段： (1)：当j不是i的子树的时候，那么i的子节点x就有两种选择，一个是选择x的子树中的消防站，那么f[i][j]=best[x]。另 一种就是选择在x外的节点作为负责站，呢们根据上面个的那个性质我们可以知道i的负责站跟x的一样，那么f[i][j]=f[x][j]。 f[i][j]+=min(f[x][j],best[x]); (2):选择i节点建消防站。 f[i][i]+=cost[i]+min(best[x],f[x][i]); (3):选择i节点的子树为负责站，其实这种情况跟第一种很像 f[i][j]+=min(f[k][i]-cost[j],best[k])+cost[j]; 这样以后我们就可以求解了。
#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>const int maxn=1e6+10;const int inf=0x3f3f3f3f;using namespace std;int cost[maxn],limit[maxn],best[maxn],dp[1010][1010],cont,head[5010],dis[1010][1010],now,n;struct zp{ int u,v,w,Next;} node[maxn];void init(){ memset(head,-1,sizeof(head)); cont=0; memset(best,0x3f3f,sizeof(best)); memset(dp,0x3f3f,sizeof(dp));}void add(int u,int v,int w)//建图{ node[cont].u=u,node[cont].v=v,node[cont].w=w; node[cont].Next=head[u]; head[u]=cont++;}void getdis(int u,int fa,int len)//计算任意两点之间的距离{ dis[now][u]=len; for(int i=head[u]; i!=-1; i=node[i].Next) { int v=node[i].v; int w=node[i].w; if(v!=fa) getdis(v,u,len+w); }}void solve(int u,int fa){ for(int i=head[u]; i!=-1; i=node[i].Next)//先递归，计算，从下往上 { int v=node[i].v; if(v!=fa) solve(v,u); } for(int i=1; i<=n; i++) { if(dis[u][i]<=limit[u])//如果i点可以照顾到u点 { dp[u][i]=cost[i]; for(int j=head[u]; j!=-1; j=node[j].Next)//遍历u点的所有子节点 { int v=node[j].v; if(v!=fa) dp[u][i]+=min(dp[v][i]-cost[i],best[v]); } best[u]=min(best[u],dp[u][i]); } }}int main(){ int ncase; scanf("%d",&ncase); while(ncase--) { init(); scanf("%d",&n); for(int i=1; i<=n; i++) scanf("%d",&cost[i]); for(int i=1; i<=n; i++) scanf("%d",&limit[i]); for(int i=1; i<n; i++) { int a,b,c; scanf("%d%d%d",&a,&b,&c); add(a,b,c); add(b,a,c); } for(int i=1; i<=n; i++) { now=i; getdis(i,0,0); } solve(1,0); PRintf("%d/n",best[1]); }}新闻热点
疑难解答
