GRAPH_ – SPOJ

February 9, 2016 by Leave a Comment

Đề bài: http://vn.spoj.com/problems/GRAPH_/

Thuật toán: Đây là bài tập cơ bản về thuật toán tìm cầu, khớp. Bạn có thể tham khảo thuật toán trong ebook Giải thuật và lập trình của thầy Lê Minh Hoàng.

Code:

uses math;
const
  fi='';
  fo='';
  maxn=10000;
  maxm=50000;
  oo=trunc(1e9);
var
  link,head,ke : array[-maxm..maxm] of longint;
  i,j,n,m,kq1,kq2 : longint;
  cau,khop : longint;
  iscut : array[1..maxn] of boolean;
  count : longint;
  cha,num,low : array[1..maxn] of longint;
  free : array[-maxm..maxm] of boolean;
  nchild : array[1..maxn] of longint;
procedure add(i,u,v:longint);
begin
    link[i] :=head[u];
    head[u] := i;
    ke[i]:=v;
end;
procedure enter;
var u,v : longint;
begin
   assign(input,fi);reset(input);
   readln(n,m);
   for i:=1 to m do
     begin
         read(u,v);
         add(i,u,v);
         add(-i,v,u);
     end;
   close(input);
end;
procedure dfs(u:longint);
var i,j,v : longint;
begin
   inc(count);
   num[u]:=count;
   low[u]:=oo;
   i := head[u];
   while i<>0 do
     begin
         if free[i] then
         begin
         v := ke[i];
         free[-i] := false;
         if cha[v]=0 then
           begin
               cha[v]:=u;
               dfs(v);
               low[u] := min(low[v],low[u]);
           end
           else
           begin
               low[u] := min(low[u],num[v]);
           end;
         end;
         i := link[i];
     end;
end;
procedure process;
var i,u,v : longint;
begin
    fillchar(free,sizeof(free),true);
    fillchar(cha,sizeof(cha),0);
    for i:=1 to n do
        if cha[i]=0 then
          begin
              cha[i] := -1;
              dfs(i);
          end;
    for v:=1 to n do
      begin
          u:=cha[v];
          if (u<>-1) and (low[v]>=num[v]) then
                begin
                    inc(cau);
                end;
      end;
    for v:=1 to n do
      if cha[v]<>-1 then
        begin
          inc(nchild[cha[v]]);
        end;
    fillchar(iscut,sizeof(iscut),false);
    for v:=1 to n do
        if cha[v] <> -1 then
        begin
          u := cha[v];
          if low[v]>=num[u] then
            iscut[u]:= iscut[u] or (cha[u]<>-1) or (nchild[u]>=2);
        end;
    for v:=1 to n do
      if iscut[v] then inc(khop);
end;
procedure print;
begin
    assign(output,fo);rewrite(output);
    writeln(khop,' ',cau);
    close(output);
end;
begin
    enter;
    process;
    print;
end.
Chủ đề: DFS, SPOJ, Thuật toán Mức độ:

SPOJ – DHTABLE2

February 9, 2016 by Leave a Comment

Đề bài: http://vn.spoj.com/problems/DHTABLE2/

Thuật toán:

  • (đang cập nhập)

Code:

var t:int64;
    n:integer;
    f:text;
procedure nhap;
begin
   assign(f,'');reset(f);
   read(f,n,t);
   close(f);
end;
 
procedure xuli;
var i:longint;
    x,l:string;
    mu,k,m
    :int64;
begin
    assign(f,'');rewrite(f);
    mu:=1; i:=0;
    while t>9*mu*(i+1) do
          begin
              dec(t,9*mu*(i+1));
              inc(i);
              mu:=mu*10;
          end;
    inc(i);
    k:=mu+(t-1) div i;
    t:=t mod i;
    x:='';
    while (length(x)<n) and (k>0) do
        begin
            m:=k;
            str(m,l);
            x:=l+x;
            if t>0 then
               begin
                   delete(x,t+1,i-t);
                   t:=0;
               end;
            dec(k);
        end;
    while length(x)>n do delete(x,1,1);
    while length(x)<n do x:=' '+x;
    write(f,x);
    close(f);
end;
 
begin
  nhap;
  xuli;
end.
Chủ đề: SPOJ