ac1215.pas

同济大学 Online在线题库 AC源代码合集 程序设计竞赛必看资料

program tju1215;
const
  maxn=300;
  inf=99999999;
var
  e:array[1..maxn*2-2]of record pre,v2:word;weight:longint;end;
  last,size:array[1..maxn]of word;
  big,small:array[1..maxn,0..maxn]of longint;
  n,m,k,i,x,y,z:longint;
procedure dp(x:word);
  var
    y,w,i,j,t:longint;
  begin
    size[x]:=1;
    big[x,0]:=inf;big[x,1]:=0;
    small[x,0]:=0;small[x,1]:=inf;
    while last[x]>0 do begin
      y:=e[last[x]].v2;w:=e[last[x]].weight;last[x]:=e[last[x]].pre;
      if size[y]>0 then continue;
      dp(y);
      t:=size[x];inc(size[x],size[y]);if size[x]>k then size[x]:=k;
      for i:=t+1 to size[x] do begin big[x,i]:=inf;small[x,i]:=inf;end;
      for i:=size[x] downto 0 do begin
        inc(big[x,i],small[y,0]);if big[x,i]>inf then big[x,i]:=inf;
        inc(small[x,i],small[y,0]);if m=2 then inc(small[x,i],w);if small[x,i]>inf then small[x,i]:=inf;
        for j:=1 to size[y] do begin
          if j>i then break;
          t:=big[x,i-j]+big[y,j]+w;if t<big[x,i] then big[x,i]:=t;
          t:=big[x,i-j]+small[y,j];if t<big[x,i] then big[x,i]:=t;
          t:=small[x,i-j]+big[y,j];if t<small[x,i] then small[x,i]:=t;
          t:=small[x,i-j]+small[y,j];if m=2 then inc(t,w);if t<small[x,i] then small[x,i]:=t;
        end;
      end;
    end;
  end;
begin
  repeat
    readln(n,m,k);
    if n<k+m-1 then begin
      writeln(-1);
      for i:=2 to n do readln;
      continue;
    end;
    for i:=1 to n-1 do begin
      read(x,y,z);
      with e[i*2-1] do begin v2:=y;weight:=z;pre:=last[x];end;last[x]:=i*2-1;
      with e[i*2] do begin v2:=x;weight:=z;pre:=last[y];end;last[y]:=i*2;
    end;
    fillchar(size,sizeof(size),0);
    dp(1);
    writeln(big[1,k]);
  until seekeof;
end.