POJ 2152(树形DP)

这题告诉我一个道理：数组开得太小会出现Time Limit Exceeded

言归正传：这题的DP方程是f[x,i]:=w[i]+∑(best[y],f[y,i]-w[i]) //f[x,i]指 x 的供应站为 i 时，x子树全取的最小代价

best[y]表示min(best[y,i]) 预处理

y为x的儿子

如果x的子树有重叠的供应站，那么这个供应站只能是x的供应站i

多叉树可以用边表存的（难道树形DP=DFS？）

《一张一弛,解题之道——“约制、放宽”方法在解题中的应用》

http://www.doc88.com/p-670874250550.html

Program p2152;
var
   t,n,i,j,u,v,w2,tot,root,father:longint;
   d,w,best,dis:array[1..2000] of longint;
   head,tail,edge,we:array[1..2000] of longint;
   f:array[1..1000,1..1000] of longint;
function min(a,b:longint):longint;
begin
   if a<b then exit(a) else exit(b);
end;
procedure addedge(u,v,w:longint);
var
   i,j:longint;
begin
   inc(tot);
   we[tot]:=w;
   edge[tot]:=v;
   tail[tot]:=head[u];
   head[u]:=tot;
end;
procedure calcdis(x:longint);
var
   i,p:longint;
begin
   p:=head[x];
   while (p<>0) do
   begin
      if (dis[edge[p]]=-1) then
      begin
         dis[edge[p]]:=dis[x]+we[p];
         calcdis(edge[p]);
      end;
      p:=tail[p];
   end;
end;
procedure dfs(x,fa:longint);
var
   i,j,p:longint;
begin
   best[x]:=maxlongint;
   p:=head[x];
   while (p<>0) do
   begin
      if (edge[p]<>fa) then dfs(edge[p],x);
      p:=tail[p];
   end;
   for i:=1 to n do dis[i]:=-1;
   dis[x]:=0;

   calcdis(x);


   for i:=1 to n do
   begin
      if (dis[i]>d[x]) then f[x,i]:=maxlongint
      else
      begin
         f[x,i]:=w[i];
         p:=head[x];
         while (p<>0) do
         begin
            if (edge[p]<>fa) then inc(f[x,i],min(best[edge[p]],f[edge[p],i]-w[i]));
            p:=tail[p];
         end;
         best[x]:=min(best[x],f[x,i]);




      end;


   end;
end;
begin
   read(t);
   while t>0 do
   begin
      tot:=0;
      fillchar(head,sizeof(head),0);
      fillchar(tail,sizeof(tail),0);

      read(n);
      for i:=1 to n do read(w[i]);
      for i:=1 to n do read(d[i]);
      for i:=1 to n-1 do begin read(u,v,w2); addedge(u,v,w2); addedge(v,u,w2); end;

      root:=1;
      dfs(1,-1);
      writeln(best[root]);

      dec(t);
   end;
end.