Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

1A了.

Posted by czz5242199 at 2009-04-07 13:17:38 on Problem 1655
type node=^ts; ts=record data:longint; next:node; end;
var tmpson,son:array[0..20000] of node;
    fmax,fsum,q:array[0..20000] of longint;
    getin:array[0..20000] of boolean;
    t,tt,i,k,j,n,u,v,ans,num:longint;
    p:node;
function max(a,b:longint):longint;
  begin
    if a>b then max:=a else max:=b;
  end;
procedure dfs(num:longint);
  var p:node; j:longint;
  begin
    p:=son[num];
    while p<>nil do
    with p^ do
    begin
      dfs(data);
      if fsum[data]>fmax[num] then fmax[num]:=fsum[data];
      inc(fsum[num],fsum[data]);
      p:=next;
    end;
    inc(fsum[num]);
  end;
procedure add1(a,b:longint);
  var p:node;
  begin
    p:=son[b];
    if p=nil then begin new(son[b]); son[b]^.data:=a; son[b]^.next:=nil; exit; end;
    while p^.next<>nil do p:=p^.next;
    new(p^.next); p:=p^.next; p^.data:=a; p^.next:=nil;
  end;
procedure bfs;
  var i,k,j,l,r,now:longint; p:node;
  begin
    fillchar(getin,sizeof(getin),0);
    l:=0; r:=1; getin[1]:=true; q[1]:=1;
    repeat
      inc(l); now:=q[l];
      p:=tmpson[now];
      while p<>nil do
      with p^ do
      begin
        if not getin[data] then begin add1(data,now); inc(r); q[r]:=data; end;
        getin[data]:=true; p:=next;
      end;
    until l>=r;
  end;
procedure add(a,b:longint);
  var p:node;
  begin
    p:=tmpson[b];
    if p=nil then begin new(tmpson[b]); tmpson[b]^.data:=a; tmpson[b]^.next:=nil; end else
    begin
      while (p^.next<>nil) do p:=p^.next;
      new(p^.next); p:=p^.next; p^.data:=a; p^.next:=nil;
    end;
  end;
begin
  readln(T);
  for tt:=1 to T do
  begin
    readln(n);
    for i:=1 to n do
    begin
      if tmpson[i]<>nil then begin dispose(tmpson[i]); tmpson[i]:=nil; end;
      if son[i]<>nil then begin dispose(son[i]); son[i]:=nil; end;
    end;
    for i:=1 to n-1 do
    begin
      readln(u,v);
      add(v,u); add(u,v);
    end;
    fillchar(fsum,sizeof(fsum),0);
    fillchar(fmax,sizeof(fmax),0);
    bfs;
    dfs(1); num:=0; ans:=maxlongint;
    for i:=1 to n do
    if max(fsum[1]-fsum[i],fmax[i])<ans then begin ans:=max(fsum[1]-fsum[i],fmax[i]); num:=i; end;
    writeln(num,' ',ans);
  end;
end.

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator