TJALG – SPOJ

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

Thuật toán:

  • Bài này thuần sử dụng thuật toánn Tarjan. Thuật toán Tarjan đơn thuần dựa trên thuật toán duyệt đồ thị DFS.
  • Các bạn có thể tham khảo thuầ toán Tarjan trong sách của thầy Lê Minh Hoàng

Code:

uses math;
const
  fi='';//spa.inp';
  fo='';//spa.out';
  maxn=trunc(1e5);
  maxm=trunc(1e6);
  oo=trunc(1e9);
var
  i,j,n,m,tpltm,top,tg,count : longint;
  link,head,ke : array[1..maxm] of longint;
  low,num : array[1..maxn] of longint;
  st : array[1..maxm*10] of longint;
  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 : longint;
  begin
    assign(input,fi);reset(input);
    readln(n,m);
    for i:=1 to m do
      begin
        read(u,v);
        add(i,u,v);
      end;
  end;
function pop : longint;
  begin
    pop := st[top];
    dec(top);
  end;
procedure push(x : longint);
  begin
    inc(top);
    st[top] := x;
  end;
procedure dfs(u : longint);
  var i,v : longint;
  begin
    inc(count);
    num[u] := count;
    low[u] := count;
    push(u);
    i := head[u];
    while I<>0 do
      begin
        v := ke[i];
        if cx[v] then
        if num[v]=0 then
          begin
            dfs(v);
            low[u] := min(low[u],low[v]);
          end
          else
          begin
            low[u] := min(low[u],num[v]);
          end;
        i := link[i];
      end;
    if low[u]=num[u] then
      begin
        inc(tpltm);
        repeat
          v := pop;
          cx[v] := false;
        until v=u;
      end;
  end;
procedure process;
  var i : longint;
  begin
    fillchar(cx,sizeof(cx),true);
    for i:=1 to n do
      if num[i]=0 then
        begin
          dfs(i);
        end;
  end;
procedure print;
  begin
    assign(output,fo);rewrite(output);
    writeln(tpltm);
    close(output);
  end;
begin
  enter;
  process;
  print;
end.

WEATHER – SPOJ

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

Thuật toán:

  • Bài này sử dụng thuật toán duyệt đồ thị DFS. Bạn có thể đọc code để hiểu rõ hơn.

Code:

{$inline on}
var
               n, m        :     longint;
               a           :     array[0..100, 0..100] of boolean;
               trace       :     array[0..100] of boolean;
               count       :     longint;
 
procedure      enter;
   var i, j, u, v: longint;
   begin
      readln(n);
      for i:= 1 to n do
         for j:= 1 to n do a[i, j]:= false;
      readln(m);
 
      for i:= 1 to m do
         begin
            readln(u, v);
            a[u, v]:= true;
            a[v, u]:= true;
         end;
   end;
 
procedure      dfs(u: longint);
   var i: longint;
   begin
      inc(count);
      trace[u]:= true;
 
      for i:= 1 to n do
         if a[u, i] and (not trace[i]) then dfs(i);
   end;
 
procedure      solve;
   var i, j, res, k: longint;
   begin
      res:= 0;
 
      for i:= 1 to n do
         for j:= i + 1 to n do
            if a[i, j] then
               begin
                  a[i, j]:= false;
                  a[j, i]:= false;
 
                  for k:= 1 to n do trace[k]:= false;
                  count:= 0;
                  dfs(1);
 
                  res:= res + count*(n - count);
 
                  a[i, j]:= true;
                  a[j, i]:= true;
               end;
      writeln(res);
   end;
 
begin
   enter;
   solve;
end.

CENTRE28 – SPOJ

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

Thuật toán:

  • Tìm đường đi ngắn nhất giữa đỉnh 1 đến mọi đỉnh và giữa đỉnh n đến mọi đỉnh sử dụng thuật toán Dijkstra. Đồng thời ta tính số đường đi ngắn nhất.
  • Gọi d1[i] là đường đi ngắn nhất từ đỉnh 1 đến i
  • Gọi d2[i] là đường đi ngắn nhất từ đỉnh n đến i
  • Gọi f1[i] là số đường đi ngắn nhất từ đỉnh 1 đến i
  • Gọi f2[i] là số đường đi ngắn nhất từ đỉnh n đến i
  • Điều kiện để đỉnh i có thể làm trung tâm kinh tế thứ 3 là: (d1[i]+dn[i]<>d1[n]) hoặc (f1[i]*fn[i]<>f1[n])

Code:

Pascal

const   fi      ='';
        fo      ='';
        maxn    =30000+3;
        maxc    =trunc(1e9)+3;
        maxm    =trunc(1e5);
type    arrd    =array[1..maxn] of longint;
        arrf    =array[1..maxn] of int64;
        arrk    =array[-maxm..maxm] of longint;
        arrh    =array[1..maxn] of longint;
var     d1,dn,d   :arrd;
        f1,fn,f   :arrf;
        n,i,j,m   :longint;
        res     :longint;
        ans     :arrd;
        head :array[1..maxn] of longint;
        link,ts,ke    :arrk;
        // dijkstra heap;
        h,p     :array[1..maxn] of longint;
        nh      :longint;
procedure add(i,u,v,w:longint);
begin
        link[i]:=head[u];
        head[u]:=i;
        ke[i]:=v;
        ts[i]:=w;
end;
procedure enter;
var     u,v,w:longint;
begin
        assign(input,fi);reset(input);
        readln(n,m);
        for i:=1 to m do
                begin
                        read(u,v,w);
                        add(i,u,v,w);
                        add(-i,v,u,w);
                end;
        close(input);
end;
procedure swap(var x,y:longint);
var     tg:longint;
begin
        tg:=x;x:=y;y:=tg;
end;
procedure upheap(i:longint);
var     j:longint;
begin
        j:=i div 2;
        if i>1 then
        if d[h[i]] < d[h[j]] then
                begin
                        swap(h[i],h[j]);
                        swap(p[h[i]],p[h[j]]);
                        upheap(j);
                end;
end;
procedure downheap(i:longint);
var     j:longint;
begin
        j:=i + i;
        if j>nh then exit;
        if (j<nh) and (d[h[j]] > d[h[j+1]]) then inc(j);
        if d[h[j]] < d[h[i]] then
                begin
                        swap(h[i],h[j]);
                        swap(p[h[i]],p[h[j]]);
                        downheap(j);
                end;
end;
procedure push(i:longint);
begin
        inc(nh);
        h[nh]:=i;
        p[i]:=nh;
        upheap(nh);
end;
function pop:longint;
begin
        pop:=h[1];
        h[1]:=h[nh];
        p[h[1]]:=1;
        dec(nh);
        downheap(1);
end;
procedure update(i:longint);
begin
        if p[i]=0 then push(i) else upheap(p[i]);
end;
procedure dijkstra(s:longint);
var     u,v,i:longint;
begin
        fillchar(h,sizeof(f),0);
        fillchar(p,sizeof(p),0);
        nh:=0;
        fillchar(f,sizeof(f),0);
        for i:=1 to n do d[i]:=maxc;
        d[s]:=0;
        f[s]:=1;
        push(s);
        repeat
                u:=pop;
                i:=head[u];
                while i<>0 do
                        begin
                                v:=ke[i];
                                if d[v]>d[u]+ts[i] then
                                        begin
                                                d[v]:=d[u]+ts[i];
                                                f[v]:=f[u];
                                                update(v);
                                        end
                                        else
                                if d[v]=d[u]+ts[i] then
                                        begin
                                                f[v]:=f[u]+f[v];
                                        end;
                                i:=link[i];
                        end;
        until nh=0;
end;
procedure process;
begin
        dijkstra(1);
        f1:=f;
        d1:=d;
        dijkstra(n);
        fn:=f;
        dn:=d;
        for i:=1 to n do
                if (d1[i]+dn[i]<>d1[n])
                or (f1[i]*fn[i]<>f1[n]) then
                        begin
                                inc(res);
                                ans[res]:=i;
                        end;
end;
procedure print;
begin
        assign(output,fo);rewrite(output);
        {for i:=1 to n do writeln(d1[i]);}
        writeln(res);
        for i:=1 to res do writeln(ans[i]);
        close(output);
end;
begin
        enter;
        process;
        print;
end.

C++

#include <bits/stdc++.h>
#define FORE(i, a, b) for(int i = a; i <= b; i++)
#define FORD(i, a, b) for(int i = a; i >= b; i--)
#define FOR(i, a, b) for(int i = a; i < b; i++)
const int MAXN = 1e5 * 5;
const int INF = 1e9 + 7;
 
using namespace std;
int n, m;
struct data{
    int u, w;
    bool operator <(const data &op) const
    {
        return w > op.w;
    }
};
vector< data > adj[MAXN];
priority_queue<data, vector<data> > q;
int d[3][MAXN];
long long f[3][MAXN];
void min_path(int cs, int s)
{
    FORE(u, 1, n) d[cs][u] = INF;
    d[cs][s] = 0; f[cs][s] = 1;
    q.push((data){s, 0});
    while (q.size()){
        int u = q.top().u;
        int cost_to_u = q.top().w;
        q.pop();
        if (cost_to_u != d[cs][u]) continue;
        FOR(i, 0, adj[u].size()){
            int v = adj[u][i].u;
            int w = adj[u][i].w;
            if (d[cs][v] > d[cs][u] + w){
                d[cs][v] = d[cs][u] + w;
                f[cs][v] = f[cs][u];
                q.push((data){v, d[cs][v]});
            }
            else
            if (d[cs][v] == d[cs][u] + w) f[cs][v] += f[cs][u];
        }
    }
}
vector< int > ans;
int main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    #ifndef ONLINE_JUDGE
    freopen("CENTRE.inp", "r", stdin);
    freopen("CENTRE.out", "w", stdout);
    #endif //MIKELHPDATKE
    cin >> n >> m;
    int u, v, w;
    FORE(i, 1, m){
        cin >> u >> v >> w;
        adj[u].push_back((data){v, w});
        adj[v].push_back((data){u, w});
    }
    min_path(1, 1);
    min_path(2, n);
    FORE(u, 1, n) if (d[1][u] + d[2][u] > d[1][n] || (d[1][u] + d[2][u] == d[1][n] && 1ll * f[1][u] * f[2][u] < f[1][n])) ans.push_back(u);
    cout << ans.size() << endl;
    FOR(i, 0, ans.size()) cout << ans[i]<<endl;
    return 0;
}

DHFRBUS – SPOJ

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

Thuật toán:

  • Sử dụng thuật toán tìm đường đi ngắn nhất dijkstra.
  • Gọi d[u,x] là quãng đường ngắn nhất đi từ s đến u khi dùng x vé xe miến phí
  • Kết quả là d[t,k].

Code:

{$inline on}
 
const   fi      ='';
        fo      ='';
        maxN    =trunc(1e5)*2;
        maxM    =trunc(1e5)*10;
        maxK    =5;
        oo       =2*trunc(1e12);
type    Tadj    =record
                v,w,link:int64;
        end;
 
        THeap   =record
                v1,v2:int64;
        end;
 
        Arr1    =array[0..maxN] of int64;
        Arr2    =array[0..maxM] of Tadj;
        Arr4    =array[0..maxN*maxK] of THeap;
        Arr5    =array[0..maxN,0..maxK] of int64;
 
var     n, m, k :longint;
        Adj     :arr2;
        Head    :arr1;
        s, t    :longint;
        d       :arr5;
        Pos     :arr5;
        H       :arr4;
        nHeap   :longint;
        c       :longint;
//heapmin;
procedure hv(var a, b:int64);
var     tg      :int64;
begin
        tg:=a;a:=b;b:=tg;
end;
 
procedure UpHeap(i:longint);
begin
 
        if (i<=1) or (d[H[i div 2].v1,H[i div 2].v2]<=d[H[i].v1,H[i].v2]) then exit;
        hv(Pos[H[i div 2].v1,H[i div 2].v2],Pos[H[i].v1,H[i].v2]);
        hv(H[i div 2].v1,H[i].v1);
        hv(H[i div 2].v2,H[i].v2);
        UpHeap(i div 2);
end;
 
procedure DownHeap(i:longint);
var     j :longint;
begin
        j:=i*2;
        if j>nHeap then exit;
        if (j<nheap) and (d[H[j+1].v1,H[j+1].v2]<d[H[j].v1,H[j].v2]) then inc(j);
        if d[H[i].v1,H[i].v2]<=d[H[j].v1,H[j].v2] then exit;
        hv(Pos[H[i].v1,H[i].v2],Pos[H[j].v1,H[j].v2]);
        hv(H[i].v1,H[j].v1);
        hv(H[i].v2,H[j].v2);
        DownHeap(j);
end;
 
procedure Update(u,x:longint);
var     p :longint;
begin
        p:=pos[u,x];
        if p=0 then
                begin
                        inc(nHeap);
                        H[nheap].v1:=u;
                        H[nheap].v2:=x;
                        Pos[u,x]:=nHeap;
                        p:=nHeap;
                end;
        UpHeap(p);
end;
 
procedure GetMin(var u, x:longint);
begin
        if nheap=0 then
                begin
                        u:=0;x:=0;
                        exit;
                end;
        u:=H[1].v1;x:=H[1].v2;
        H[1].v1:=H[nHeap].v1;
        H[1].v2:=H[nheap].v2;
        Pos[H[1].v1,H[1].v2]:=1;
        dec(nHeap);
        downHeap(1);
end;
 
procedure Dijkstra;
var      i, v, w      :int64;
        ans     :int64;
        u     ,x  :longint;
begin
        fillchar(pos,n,0);
        for u:=1 to n do
                for x:=0 to k do d[u,x]:=oo;
        nHeap:=0;
        d[s,0]:=0;
        Update(s,0);
        repeat
                GetMin(u,x);
                i:=head[u];
                if u=0 then exit;
                while i<>0 do
                begin
                        v:=adj[i].v;
                        w:=adj[i].w;
                        if d[v,x]>d[u,x]+w then
                        begin
                                d[v,x]:=d[u,x]+w;
                                Update(v,x);
                        end;
                        if (x<k) and (d[v,x+1]>d[u,x]) then
                        begin
                                d[v,x+1]:=d[u,x];
                                Update(v,x+1);
                        end;
                        i:=adj[i].link;
                end;
        until nHeap=0;
        ans:=oo;
        ans:=d[t,k];
        {for x:=0 to k do
                if d[t,x]<ans then
                                ans:=d[t,x];}
        writeln(ans);
end;
 
procedure Tadd(u,v,w:longint);
begin
        inc(c);
        Adj[c].v:=v;
        Adj[c].w:=w;
        Adj[c].link:=head[u];
        head[u]:=c;
end;
 
procedure xuly;
var     i, u, v, w      :longint;
begin
        assign(input,fi);assign(output,fo);
        reset(input);rewrite(output);
        readln(n, m, k, s, t);
        c:=0;
        fillchar(head,sizeof(head),0);
        for i:=1 to m do
                begin
                        readln(u,v,w);
                        Tadd(u,v,w);
                        Tadd(v,u,w);
                end;
        Dijkstra;
        close(input);close(output);
end;
 
begin
        xuly;
end.