2011.8.26  21:59

       题目：有向树K中值问题

       背景：NOIP算法复习试题书

       级别：NOIP

       难度：3.4

       算法：树形动态规划+记忆化搜索

       数据结构：多叉树转二叉树

       做题时间：90分钟

       编程任务：给定一棵有向树T，树T 中每个顶点u都有一个权w(u)；树的每条边(u,v)也都有一个

非负边长d(u,v)。有向树T的每个顶点u 可以看作客户，其服务需求量为w(u)。每条边(u,v)的边长d(u,v) 可以看作运输费用。如果在顶点u 处未设置服务机构，则将顶点u 处的服务需求沿有向树的边(u,v)转移到顶点v 处服务机构需付出的服务转移费用为w(u)*d(u,v)。树根处已设置了服务机构，现在要在树T中增设k处服务机构，使得整棵树T 的服务转移费用最小。对于给定的有向树T，编程计算在树T中增设k处服务机构的最小服务转移费用。

        一开始想的是二维的状态f[t,k]表示节点t分到了k个设置服务机构任务，但是发现有一个服务转移费用，它会根据距离的变化而变化，而假如说同样是t号节点分到了k个服务机构，那么如果t号节点不设置服务机构，那么他的服务转移费用要找到v（v号点指与t号点间接或直接相连并且设置了服务机构）号点，但是v号点也是不确定位置的，状态表示不完全，所以要加设一维表示离t号点最近的v号点，那么这样f[t,p,k]:=min(Σdfs(son[t],p,k)+dis[t,p]*tree[t].data{t号节点不设置服务机构}       , Σdfs(son[t],t,k-1) {在t号点设置服务机构}        )  .   

        服务转移费用可以先用Floyd预处理好.

===========================================================

代码：

type

  tre=record

    l,r,f,d,data:longint;

  end;

//==========================================

var

  f:array[-5..200,-1..200,-1..200] of longint;

  map:array[0..200,0..200] of longint;

  tree:array[0..2000] of tre;

  ans,n,m:longint;

//==========================================

function min(x,y:longint):longint;

begin

  if x<y then exit(x)

    else exit(y);

end;

//==========================================

procedure build(now,d,f,data,t:longint);{递归建树方法}

begin

  if (tree[t].l=-1) and (t=f) then

     begin

       tree[t].l:=now;

       tree[now].data:=data;

       tree[now].f:=f;

       tree[now].d:=d;{儿子到父亲节点的距离}

       exit;

     end;

  if (tree[t].l<>-1) and (t=f)then

     begin

       build(now,d,f,data,tree[t].l);

       exit;

     end;

     

  if (tree[t].r=-1) and (t<>f) then

     begin

       tree[t].r:=now;

       tree[now].data:=data;

       tree[now].f:=f;

       tree[now].d:=d;

       exit;

     end;

     

  if (tree[t].r<>-1) and (t<>f) then

     begin

       build(now,d,f,data,tree[t].r);

       exit;

     end;

end;

//==========================================

procedure init;

var

  td,tf,tdata,i:longint;

begin

  fillchar(tree,sizeof(tree),255);

  fillchar(map,sizeof(map),5);

  readln(n,m);

  

  for i:=1 to n do

    begin

      readln(tdata,tf,td);

     // build(i,td,tf,tdata,tf);{递归建树方法}

      if tree[tf].l=-1 then{非递归O(1)建树方法}

         begin

           tree[tf].l:=i;

           tree[i].data:=tdata;

           tree[i].d:=td;

           tree[i].f:=tf;

         end

      else

        begin

          tree[i].r:=tree[tf].l;

          tree[tf].l:=i;

          tree[i].data:=tdata;

          tree[i].d:=td;

          tree[i].f:=tf;

        end;

         

         

      map[i,tf]:=td;

    end;

end;

//==========================================

procedure floyd;{Floyd预处理服务转移费用}

var

  i,j,k:longint;

begin

  for k:=0 to n do

    for i:=0 to n do

      for j:=0 to n do

        if (i=j) or (j=k) or (k=i) then continue

        else

          map[i,j]:=min(map[i,j],map[i,k]+map[k,j]);

end;

//==========================================

function dfs(t,jin,k:longint):longint;

var

  temp,i:longint;

begin

  if f[t,jin,k]<f[-1,0,0] then exit(f[t,jin,k]);{记忆化搜索}

  for i:=0 to k do{t号节点不设置服务机构}

    begin

      temp:=0;

      if tree[t].l<>-1 then inc(temp,dfs(tree[t].l,jin,i));

      if tree[t].r<>-1 then inc(temp,dfs(tree[t].r,jin,k-i));

      if temp+map[t,jin]*tree[t].data<f[t,jin,k] then f[t,jin,k]:=temp+map[t,jin]*tree[t].data;

    end;

  for i:=0 to k-1 do{t号节点设置服务机构}

    begin

      temp:=0;

      if tree[t].l<>-1 then inc(temp,dfs(tree[t].l,t,i));

      if tree[t].r<>-1 then inc(temp,dfs(tree[t].r,jin,k-1-i));

      if temp<f[t,jin,k] then f[t,jin,k]:=temp;

    end;

  exit(f[t,jin,k]);

end;

//==========================================

procedure main;

var

  i:longint;

begin

  floyd;

  fillchar(f,sizeof(f),100);

  f[0,0,m]:=0;

  ans:=dfs(tree[0].l,0,m);

  writeln(ans);

end;

//==========================================

begin

  //assign(output,'c:\in.txt'); rewrite(output);

//  assign(input,'c:\out.txt'); reset(input);

  assign(input,'kmt.in'); reset(input);

  assign(output,'kmt.out'); rewrite(output);

  

  init;

  main;

  

  close(input); close(output);

end.