NTPFECT - Đại diện hoàn hảo

Tác giả: RR

Ngôn ngữ: Pascal

{$MODE OBJFPC}

uses math;
const
  FINP          =       '';
  FOUT          =       '';
  MAXN          =       1011;

type
  list          =       ^node;
  node          =       record
        u       :       longint;
        next    :       list;
  end;

var
  f1,f2         :       text;
  n             :       longint;
  ke            :       array[1..MAXN] of list;
  f,g,h         :       array[1..MAXN] of longint;
  visited       :       array[1..MAXN] of boolean;

procedure openF;
    begin
      assign(f1,FINP); reset(f1);
      assign(f2,FOUT); rewrite(f2);
    end;

procedure closeF;
    begin
      close(f1);
      close(f2);
    end;

procedure add(u:longint; var a:list);
    var
      p:list;
    begin
      new(p); p^.u:=u;
      p^.next:=a; a:=p;
    end;

procedure del(var a:list);
    begin
      if a=nil then exit;
      del(a^.next);
      dispose(a);
    end;

procedure inp;
    var
      i,u,v:longint;
    begin
      fillchar(ke,sizeof(ke),0);
      fillchar(f,sizeof(f),0);
      fillchar(g,sizeof(g),0);
      fillchar(h,sizeof(h),0);
      fillchar(visited,sizeof(visited),false);
      for i:=2 to n do
        begin
          read(f1,u,v);
          add(u,ke[v]);
          add(v,ke[u]);
        end;
    end;

procedure dfs(u:longint);
    var
      p:list;
      v,x,now:longint;
    begin
      visited[u]:=true;
      p:=ke[u]; x:=0; now:=high(longint);
      f[u]:=1;
      while p<>nil do
        begin
          v:=p^.u; p:=p^.next;
          if visited[v] then continue;
          dfs(v);

          if f[v]-min(f[v],g[v])<now then
            begin
              x:=v;
              now:=f[v]-min(f[v],g[v]);
            end;
          inc(f[u],min(min(f[v],g[v]),h[v]));
          inc(g[u],min(f[v],g[v]));
          inc(h[u],g[v]);
        end;
      if x=0 then g[u]:=MAXN
      else g[u]:=g[u]+f[x]-min(f[x],g[x]);
    end;

procedure solve;
    begin
      dfs(1);
      writeln(f2,min(f[1],g[1]));
    end;

begin
  openF;
  read(f1,n);
  while (n>0) do
    begin
      inp;
      if n<=3 then writeln(f2,1)
      else solve;
      for n:=1 to n do
        del(ke[n]);
      read(f1,n);
    end;
  closeF;
end.

Download