STONE1 – spoj

Đề bài:

Thuật toán:

  • (đang cập nhập)

Code:

const
  fi='';//stone1.inp';
  fo='';//stone1.out';
  maxn=403;
  maxm=403;
type
  arr1 = array[1..maxn] of longint;
var
  link,head,ke : array[-maxm..maxm] of longint;
  f,deg : array[1..maxn] of longint;
  i,j,n,m,k : longint;
  st : array[1..maxn,1..maxn] of longint;
  top : array[1..maxn] of longint;
  a : array[1..maxn,1..maxn] of boolean;
  cx : array[1..maxn] of boolean;
procedure add(i,u,v : longint);
  begin
    link[i] := head[u];
    head[u] := i;
    ke[i] := v;
  end;
procedure enter;
  var u,v,i : longint;
  begin
    assign(input,fi);reset(input);
    read(n);
    for i := 1 to n do
      begin
        read(u,k);
        for j:=1 to k do
          begin
            read(v);
            if a[u,v] = false then
              begin
                a[u,v] := true;
                inc(deg[u]);
              end;
            if a[v,u] = false then
              begin
                a[v,u] := true;
                inc(deg[v]);
              end;
          end;
      end;
    close(input);
  end;
procedure push(i,x : longint);
  begin
    inc(top[i]);
    st[i,top[i]] := x;
  end;
procedure swap(var x,y : longint);
  var tg : longint;
  begin
    tg:=x;x:=y;y:=tg;
  end;
procedure qs(l,r : longint; var a : arr1);
  var i,j,x : longint;
  begin
    i :=l;j:=r;
    x := a[(l+r) div 2];
    repeat
      while a[i] > x do inc(i);
      while a[j] < x do dec(j);
      if i<=j then
        begin
          swap(a[i],a[j]);
          inc(i);dec(j);
        end;
    until i>j;
    if i<r then qs(i,r,a);
    if j>l then qs(l,j,a);
  end;
procedure dfs(u : longint);
  var i,v,s : longint;
  begin
    cx[u] := false;
    if deg[u] <= 1 then begin f[u] := 1; exit; end;
    for v := 1 to n do
      if a[u,v] then
      if cx[v] then
        begin
          dfs(v);
          push(u,f[v]);
        end;
    qs(1,top[u],st[u]);
    s := st[u,1];
    v := st[u,1]-1;
    for i:= 2 to top[u] do
      if v < st[u,i] then
      begin
        s := s + (st[u,i]-v);
        v := v + (st[u,i]-v);
        v := v - 1;
      end else v := v-1;
    f[u] := s;
  end;
procedure process;
  begin
    fillchar(cx,sizeof(cx),true);
    dfs(1);
  end;
procedure print;
  begin
    assign(output,fo);rewrite(output);
    writeln(f[1]);
    close(output);
  end;
begin
  enter;
  process;
  print;
end.
Khuyên dùng

 

Speak Your Mind

*