PTREE - Cây P đỉnh ( Cơ bản )

Tác giả: ll931110

Ngôn ngữ: Pascal

{$MODE DELPHI}
program PTREE;
const
  input  = '';
  output = '';
  maxn = 200;
  maxv = 100000000;
var
  free: array[1..maxn] of boolean;
  c: array[1..maxn,1..maxn] of boolean;
  F,child: array[1..maxn,0..maxn] of integer;
  p,trace: array[1..maxn,1..maxn,0..maxn] of integer;
  n,k: integer;
  a,list,nchi: array[1..maxn] of integer;
  nlist: integer;

procedure init;
var
  fi: text;
  i,x,y,j,t: integer;
begin
  assign(fi, input);
    reset(fi);

  readln(fi, n, k);
  fillchar(c, sizeof(c), false);

  for i := 1 to n do read(fi, a[i]);
  for i := 1 to n - 1 do
    begin
      readln(fi, x, y);
      c[x,y] := true;
      c[y,x] := true;
    end;

  close(fi);

  for i := 1 to n do
    for j := 1 to n do
      for t := 1 to n do p[i,j,t] := -maxv;
  for i := 1 to n do
    for j := 1 to n do p[i,j,0] := 0;

  for i := 1 to n do
    for j := 1 to n do F[i,j] := -maxv;
  for i := 1 to n do F[i,0] := 0;

  fillchar(free, sizeof(free), true);
end;

procedure DFS(u: integer);
var
  v: integer;
begin
  free[u] := false;
  nchi[u] := 0;

  for v := 1 to n do
    if free[v] and c[u,v] then
      begin
        inc(nchi[u]);
        child[u,nchi[u]] := v;
        DFS(v);
      end;
end;

procedure dp(u: integer);
var
  i,j,t: integer;
begin
  if nchi[u] = 0 then
    begin
      F[u,1] := a[u];
      exit;
    end;

  for i := 1 to nchi[u] do dp(child[u,i]);
  for i := 0 to n do
    begin
      p[u,1,i] := F[child[u,1],i];
      trace[u,1,i] := i;
    end;

  for i := 2 to nchi[u] do
    for j := 0 to n do
      for t := 0 to j do
        if p[u,i,j] < p[u,i - 1,t] + F[child[u,i],j - t] then
          begin
            p[u,i,j] := p[u,i - 1,t] + F[child[u,i],j - t];
            trace[u,i,j] := j - t;
          end;

  for i := 1 to n - 1 do F[u,i] := p[u,nchi[u],i - 1] + a[u];
end;

procedure add(x: integer);
begin
  inc(nlist);
  list[nlist] := x;
end;

procedure track(u,val: integer);
var
  j,t: integer;
begin
  if val <= 1 then
    begin
      if val = 1 then add(u);
      exit;
    end;

  for j := nchi[u] downto 1 do
    begin
      t := trace[u,j,val - 1];
      val := val - t;
      track(child[u,j],t);
    end;
  add(u);
end;

procedure printresult;
var
  fo: text;
  i,j,t,u,max: integer;
begin
  assign(fo, output);
    rewrite(fo);

    max := -maxv;
    u := 0;
    for i := 1 to n do if max < F[i,k] then
      begin
        max := F[i,k];
        u := i;
      end;

    nlist := 0;
    track(u,k);

    for i := 1 to k - 1 do
      for j := i + 1 to k do
        if list[i] > list[j] then
          begin
            t := list[i];
            list[i] := list[j];
            list[j] := t;
          end;
    for i := 1 to k do write(fo, list[i], ' ');
  close(fo);
end;

begin
  init;
  DFS(1);
  dp(1);
  printresult;
end.

Download