STABLE – spoj

August 15, 2017 by Leave a Comment

Đề bài:

Thuật toán:

  • BFS từ đỉnh S
  • Gọi bac[i] là đồ dài đường đi ngắn nhất từ s đến i
    • bac[i] = bac[j] + 1
    • với i kề j và j duyệt BFS trước i
  • ok[i] = 1 nếu i ổn định, ok[i] = 0 nếu i không ổn định.
  • Hãy tham khảo code để biết cách kiểm tra xem i có ổn định không

Code:

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;i=i+1)
#define FORD(i,b,a) for (int i=(b),_a=(a);i>=_a;i=i-1)
#define REP(i,n) for (int i=0,_n=(n);i<_n;i=i+1)
#define FORE(i,v) for (__typeof((v).begin()) i=(v).begin();i!=(v).end();i++)
#define ALL(v) (v).begin(),(v).end()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define double db
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
const int MAXN = 1E4+3;
const int oo = 1e9+3;
 
int n, m, s, u, v, res, bac[MAXN],adj[MAXN][MAXN];
bool ok[MAXN];
queue<int> q;
vector<int> a[MAXN];
 
int main() {
    	#ifndef ONLINE_JUDGE
    	freopen("test.inp", "r", stdin);
    	freopen("test.out", "w", stdout);
    	#endif
    cin >> n >> m >> s;
    FOR(i,1,m) {
        cin >> u >> v;
        if (!adj[u][v])
            a[u].push_back(v);
        adj[u][v] = 1;
    }
    q.push(s); bac[s] = 1;
    while (!q.empty()) {
        u = q.front();
        q.pop();
        for(int i=0; i<a[u].size(); i++)
        {
            v = a[u][i];
            if (!bac[v])
            {
                if (ok[u]) ok[v] = 1;
                bac[v] = bac[u] + 1;
                q.push(v);
            }
            else
            if (bac[v] == bac[u] + 1) ok[v] = 1;
        }
    }
    FOR(i,1,n) if (ok[i]) res++;
    cout << res;
	return 0;
}
const
  fi='stable.inp';
  fo='stable.out';
  maxn=10000;
  maxm=50000;
var
  link,head,ke : array[1..maxm] of longint;
  i,j,n,m,st,ans,s,dau,cuoi,u,v : longint;
  q,bac : array[1..maxn] of longint;
  ok : array[1..maxn] of boolean;
  a : array[1..maxn,1..maxn] of boolean;
procedure push(x : longint);
  begin
    inc(cuoi);
    q[cuoi] := x;
  end;
procedure add(i,u,v : longint);
  begin
    link[i] := head[u];
    head[u] := i;
    ke[i] := v;
  end;
begin
//  assign(input,fi);reset(input);
//  assign(output,fo);rewrite(output);
  read(n,m,s);
  for i := 1 to m do
    begin
      read(u,v);
      if a[u,v] = false then
      add(i,u,v);
      a[u,v] := true;
    end;
  dau := 1; cuoi := 0;
  push(s);
  bac[s] := 1;
  while (dau <= cuoi) do
    begin
      u := q[dau];
      inc(dau);
      i := head[u];
      while i <> 0 do
        begin
          v := ke[i];
          if bac[v] = 0 then
            begin
              if ok[u] then ok[v] := true;
              bac[v] := bac[u] + 1;
              push(v);
            end
            else
          if bac[v] = bac[u] + 1 then
            begin
              ok[v] := true;
            end;
          i := link[i];
        end;
    end;
  for i := 1 to n do
    if ok[i] then inc(ans);
  writeln(ans);
//  close(input);close(output);
end.
Chủ đề: BFS, Đồ thị, SPOJ Mức độ:

UPGRANET – spoj

August 12, 2017 by Leave a Comment

Đề bài:

Thuật toán:

Ta thấy thông lượng truyền tin từ u đến v là giá trị lớn nhất của cạnh nhỏ nhất trên mọi con đường từ u đến v.
Vì vậy, ban đầu, ta sẽ xây dựng cây khung lớn nhất(tương tự như cây khung nhỏ nhất nhưng sort ngược lại).

Gọi dis(u,v) là cạnh có trọng số nhỏ nhất khi đi từ u đến v trên cây vừa tạo. Ta chọn nút 1 làm gốc, duyệt dfs để lưu trữ cạnh nhỏ nhất và các nút cha của u khi đi từ 1 đến u (đều dùng RMQ). Với mỗi 1 cạnh không nằm trong cây khung, ta tìm nút cha chung gần nhất(gọi là p), kết quả cộng thêm một lượng bằng hiệu của min(dis(u, p), dis(v, p)) và rọng số cạnh đang xét.

Code:

#include <bits/stdc++.h>
#define maxn 1000005
#define maxm 10000005
#define maxc 1000000007
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define pii pair<long long, long long>
#define fort(i, a, b) for(int i = (a); i <= (b); i++)
#define ford(i, a, b) for(int i = (a); i >= (b); i--)
#define Task "UPGRANET"
#define fast ios_base::sync_with_stdio(0);cin.tie();cout.tie();
#define stop1 {cout << "-1\n"; return;}
#define stop2 {cout << "0\n"; return;}
#define stop3 {cout << "yes\n"; exit(0);}
#define skip1 {cout << "Yes\n"; continue;}
#define skip2 {cout << "No\n"; continue;}
#define ll long long
 
using namespace std;
 
ll n, m, root[maxn], h[maxn], res;
pii  par[maxn][20];
bool dd[maxn];
vector<pair<ll, ll> > ke[maxn];
struct canh
{
    ll u, v, w;
}ed[maxn];
 
void setup()
{
    cin >> n >> m;
    fort(i, 1, m)
        cin >> ed[i].u >> ed[i].v >> ed[i].w;
}
 
bool cmp(canh p, canh q)
{
    return p.w > q.w;
}
 
ll getroot(ll u)
{
    if(root[u] == 0) return u;
    return root[u] = getroot(root[u]);
}
 
void make_tree()
{
    sort(ed+1, ed+m+1, cmp);
    fort(i, 1, m)
    {
        ll p = getroot(ed[i].u);
        ll q = getroot(ed[i].v);
        if(p == q) continue;
        root[p] = q;
        dd[i] = 1;
        ke[ed[i].u].pb(mp(ed[i].v, ed[i].w));
        ke[ed[i].v].pb(mp(ed[i].u, ed[i].w));
    }
}
 
void dfs(ll u, ll tr)
{
    fort(i, 0, int(ke[u].size()) - 1)
    {
        ll v = ke[u][i].F;
        if(v == tr) continue;
        h[v] = h[u] + 1;
        par[v][0] = mp(u,ke[u][i].S);
        fort(j, 1, 18)
        {
            par[v][j].F = par[par[v][j-1].F][j-1].F;
            par[v][j].S = min(par[par[v][j-1].F][j-1].S, par[v][j-1].S);
        }
        dfs(v, u);
    }
}
 
pii lca(ll u, ll v)
{
    pii p;
    p.S = 1ll* maxc * maxc;
    if( h[u] > h[v])
        swap(u, v);
    ll diff = h[v] - h[u];
    ford(i, 18, 0)
        if((diff >> i) & 1)
        {
            p.S = min(p.S, par[v][i].S);
            v = par[v][i].F;
 
        }
    if(v == u) return mp(u, p.S);
    ford(i, 18, 0)
        if(par[u][i].F != par[v][i].F)
        {
            p.S = min(p.S, min(par[v][i].S, par[u][i].S));
            v = par[v][i].F;
            u = par[u][i].F;
        }
    return mp(par[u][0].F, min(p.S, min(par[u][0].S, par[v][0].S)));
}
 
void work()
{
    make_tree();
    h[1] = 1;
    dfs(1, 0);
    fort(i, 1, m)
        if(!dd[i])
        {
            pii l = lca(ed[i].u, ed[i].v);
            res += max(0ll, l.S - ed[i].w);
        }
    cout << res;
}
 
 
int main()
{
    fast
  //  freopen(Task".inp", "r", stdin);
  //  freopen(Task".out", "w", stdout);
    setup();
    work();
    return 0;
}

Cowboy

Chủ đề: DFS, Đồ thị, Kruskal, LCA, Phương pháp Mức độ:

AZNET – spoj

December 4, 2016 by Leave a Comment

Đề bài:

Thuật toán:

Code:

Const   inp = '';
        out = '';
        maxn = 10001;
        maxm = 100001;
 
Var     n,m,ntest,min,max,k,res     :       longint;
        x,y,id :       array [1..2,1..maxm] of longint;
        lab :       array [1..2,1..maxn] of longint;
        sl      :   array [1..2] of longint;
        a,b :       array [0..maxn] of longint;
{***************************************************************************}
function getroot(t,u : longint) : longint;
  begin
      while lab[t,u] > 0 do u := lab[t,u];
      exit(u);
  end;
{***************************************************************************}
procedure union(t,r1,r2 : longint);
var x : longint;
  begin
      x := lab[t,r1]+lab[t,r2];
      if lab[t,r1] > lab[t,r2] then
       begin
           lab[t,r1] := r2;
           lab[t,r2] := x;
       end
      else begin
               lab[t,r2] := r1;
               lab[t,r1] := x;
           end;
  end;
{****************************************************************************}
procedure main;
var i,j,dem,u,v,r1,r2,r3,r4 : longint;
  begin
      for i := 1 to n do
        begin
            lab[1,i] := -1;
            lab[2,i] := -1;
        end;
      max := 0;
      for i := 1 to sl[1] do
        begin
           u := x[1,i]; v := y[1,i];
           r1 := getroot(1,u); r2 := getroot(1,v);
           if r1 <> r2 then
             begin
                 inc(max);
                 union(1,r1,r2);
             end;
        end;
      min := 0;
      for i := 1 to sl[2] do
        begin
            u := x[2,i]; v := y[2,i];
            r1 := getroot(1,u); r2 := getroot(1,v);
            if r1 <> r2 then
              begin
                inc(min);
                union(1,r1,r2);
                r3 := getroot(2,u); r4 := getroot(2,v);
                union(2,r3,r4);
              end;
        end;
      for i := 1 to sl[2] do
        begin
            u := x[2,i]; v := y[2,i];
            r1 := getroot(2,u); r2 := getroot(2,v);
            if r1 <> r2 then
              begin
                  inc(min);
                  union(2,r1,r2);
              end;
        end;
      min := n-1-min;
      res := maxlongint;
      for i := min to max do
        if a[i]+b[n-1-i] < res then
          begin
              res := a[i]+b[n-1-i];
              k := i;
          end;
      for i := 1 to n do
        begin
            lab[1,i] := -1; lab[2,i] := -1;
        end;
      for i := 1 to sl[1] do
        begin
           u := x[1,i]; v := y[1,i];
           r1 := getroot(1,u); r2 := getroot(1,v);
           if r1 <> r2 then union(1,r1,r2);
        end;
      dem := 0;
      for i := 1 to sl[2] do
        begin
            u := x[2,i]; v := y[2,i];
            r1 := getroot(1,u); r2 := getroot(1,v);
            if r1 <> r2 then
              begin
                write(id[2,i],' ');
                inc(dem);
                union(1,r1,r2);
                r3 := getroot(2,u); r4 := getroot(2,v);
                union(2,r3,r4);
              end;
        end;
      if dem < n-1-k then
        begin
           for i := 1 to sl[2] do
            begin
                u := x[2,i]; v := y[2,i];
                r1 := getroot(2,u); r2 := getroot(2,v);
                if r1 <> r2 then
                 begin
                     inc(dem);
                     write(id[2,i],' ');
                     union(2,r1,r2);
                     if dem=n-1-k then break;
                 end;
            end;
        end;
      for i := 1 to sl[1] do
        begin
          u := x[1,i]; v := y[1,i];
          r1 := getroot(2,u); r2 := getroot(2,v);
          if r1 <> r2 then
            begin
                write(id[1,i],' ');
                union(2,r1,r2);
            end;
        end;
      writeln;
  end;
{***************************************************************************}
procedure nhap;
var i,j,u,v,k : longint;
  begin
      assign(input,inp); reset(input);
      assign(output,out); rewrite(output);
      readln(ntest);
      while ntest > 0 do
       begin
           dec(ntest);
           readln(n,m);
           for i := 1 to n-1 do read(a[i]);
           for i := 1 to n-1 do read(b[i]);
           sl[1] := 0; sl[2] := 0;
           for i := 1 to m do
             begin
                 readln(u,v,k);
                 inc(sl[k]);
                 x[k,sl[k]] := u; y[k,sl[k]] := v;
                 id[k,sl[k]] := i;
             end;
           main;
       end;
  end;
{****************************************************************************}
begin
     nhap;
end.
Chủ đề: Đồ thị, Kruskal

PVOI14_3 – spoj

November 29, 2016 by Leave a Comment

Đề bài:

Thuật toán:

Ta có 1 công thức sau:

Gọi k là chi phí nhỏ nhất cần tìm.

Nếu tồn tại một chuyến đi để mất chi phí là k thì

(S1 + S2 + .. + Sp) / (T1 + T2 + … + Tp) = k

⇔ S1 + S2 + … + Sp – k * (T1 + T2 + … + Tp) = 0

⇔ (S1 – k * T1) + (S2 – k * T2) + … + (Sp – k * Tp) = 0.

 

Giả sử tồn tại 1 chuyến đi có chi phí km < k khi đó ta có:

kmin < k = (S1 + S2 + .. + Sp) / (T1 + T2 + … + Tp)

⇔ (S1 – kmin * T1) + (S2 – kmin * T2) + … + (Sp – kmin * Tp) > 0

 

Từ đây ta có nghĩ ra 1 thuật toán như sau.

  • Chặt nhị phân chi phí nhỏ nhất(x), với mỗi chi phí Mình tạo trọng số mỗi cho mỗi cạnh (s ,t) -> (s – x * t)
  • Nếu tồn tại 1 chu trình âm với trọng số mới -> không thể tạo ra chi phí là x.
  • Ngược lại nếu không tồn tại 1 chu trình âm nào thì kết quả cần tìm sẽ <=x
    => Chúng ta có thể sử dụng thuật toán FordBellman để tìm chu trình âm

Code:

#include <bits/stdc++.h>
 
using namespace std;
 
#define N 1010
#define M 10010
const double esp = 1e-5;
 
int n, m,  trace[N], u[M], v[M], c[M];
double d[N];
 
bool Ok(int x, int y) {
    while (x != 1){
        x = trace[x];
        if (x == 0) return false;
        if (x == y) return true;
    }
    return false;
}
bool FordBellman(double mid) {
    for (int i = 1; i<=n; i++) d[i] = 1e18;
    d[1] = 0;
    memset(trace, 0, sizeof trace);
    for (int i = 0; i<n; i++) {
        for (int j = 0; j<m; j++) {
            int x = u[j]; int y = v[j];
            if (d[y] > d[x] + c[j] - mid) {
                d[y] = d[x] + c[j] - mid;
                if (Ok(x, y)) {
                    return true;
                }
                trace[y] = x;
            }
        }
    }
    return false;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for (int i = 0; i<m; i++) {
        cin>>u[i]>>v[i]>>c[i];
    }
    double l = 0;
    double r = 1e10;
    double cur = 0;
    while (r - l >= esp) {
        double mid = (l + r) / 2;
        if (!FordBellman(mid)) {
            cur = mid;
            l = mid;
        }else r = mid;
    }
    if (abs (cur - 1e10) <=esp) {
        cout<<"NO TOUR";
    }else
    cout<<fixed<<setprecision(2)<<cur;
}
{$MODE OBJFPC}
program SmartDogContest;
const
  InputFile  = '';
  OutputFile = '';
  maxN = 1000;
  maxM = 10000;
  maxW = 1000000000;
  maxD = (maxN + 1) * maxW;
type
  TEdge = record
    u, v, c: Integer;
  end;
var
  fi, fo: TextFile;
  e: array[1..maxM] of TEdge;
  d: array[1..maxN + 1, 1..maxN] of Int64;
  n, m: Integer;
  BestMiu: Extended;
 
procedure Enter;
var
  i: Integer;
begin
  ReadLn(fi, n, m);
  for i := 1 to m do
    with e[i] do
      ReadLn(fi, u, v, c);
end;
 
procedure Init;
var
  i: Integer;
begin
  FillQWord(d, SizeOf(d) div 8, maxD);
  for i := 1 to n do
    d[1, i] := 0;
end;
 
procedure Minimize(var target: Int64; value: Int64); inline;
begin
  if target > value then target := value;
end;
 
procedure Optimize;
var
  k, i: Integer;
begin
  for k := 2 to n + 1 do //Tinh d[k, v] qua cac d[k - 1, u]
    for i := 1 to m do
      with e[i] do
        Minimize(d[k, v], d[k - 1, u] + c);
end;
 
procedure GetBest;
var
  v, k: Integer;
  min, max, trial: Extended;
begin
  min := maxD;
  for v := 1 to n do
    if d[n + 1, v] < maxD then
      begin
        max := -maxD;
        for k := 1 to n do
          if d[k, v] < maxD then
            begin
              trial := (d[n + 1, v] - d[k, v]) / (n - k + 1);
              if max < trial then max := trial;
            end;
        if max < min then
          min := max;
      end;
  BestMiu := min;
end;
 
begin
  AssignFile(fi, InputFile); Reset(fi);
  AssignFile(fo, OutputFile); Rewrite(fo);
  try
    Enter;
    Init;
    Optimize;
    GetBest;
    if BestMiu = maxD then
      Write(fo, 'NO TOUR')
    else
      Write(fo, BestMiu:0:2);
  finally
    CloseFile(fi); CloseFile(fo);
  end;
end.
Chủ đề: Đồ thị, Floyd, SPOJ Mức độ: ,

PVOI14_2 – spoj

November 29, 2016 by Leave a Comment

Đề bài:

Thuật toán:

  • (đang cập nhập)

Code:

using namespace std;
#include<bits/stdc++.h>
#define FOR(i, a, b) for (int i = a; i < b; i++)
#define FORE(i, a, b) for (int i = a; i <= b; i++)
#define FORD(i, a, b) for (int i = a; i >= b; i--)
const int MAXN = 5*1e6;
const int INF = 1e9 + 7;
typedef pair<int, int> ii;
 
int p[MAXN], a[1001][1001];
vector < ii > adj[MAXN];
int n, maxa;
 
int get(int i, int j)
{
    return (i - 1) * n + j;
}
 
int pa(int x)
{
    while (p[x] > 0) x = p[x];
    return x;
}
 
int Union(int r1, int r2)
{
    int tmp = p[r1] + p[r2];
    if (p[r1] < p[r2]){
        p[r2] = r1;
        p[r1] = tmp;
    } else{
        p[r1] = r2;
        p[r2] = tmp;
    }
    return -tmp;
}
 
int main()
{
	ios::sync_with_stdio(false); cin.tie(0);
//	freopen("RSELECT.inp", "r", stdin);
  //  freopen("RSELECT.out", "w", stdout);
    cin >> n;
    FORE(i, 1, n) FORE(j, 1, n) {
        cin >> a[i][j];
        maxa = max(maxa, a[i][j]);
    }
    FORE(i, 1, n) FORE(j, 1, n){
        int u = get(i, j);
        if (i < n) adj[abs(a[i][j] - a[i + 1][j])].push_back(ii(u, get(i + 1, j)));
        if (j < n) adj[abs(a[i][j] - a[i][j + 1])].push_back(ii(u, get(i, j + 1)));
    }
    memset(p, -1, sizeof(p));
    int ans = 0;
    FORE(ll, 0, maxa){
        FOR(i, 0, adj[ll].size()) {
            p[adj[ll][i].first] = -1;
            p[adj[ll][i].second] = -1;
           // cout<<ll<<" "<<adj[ll][i].first<<" "<<adj[ll][i].second<<endl;
        }
        FOR(i, 0, adj[ll].size()){
            int u = adj[ll][i].first, v = adj[ll][i].second;
            int r1 = pa(u), r2 = pa(v);
            if (r1 != r2) ans = max(ans, Union(r1, r2));
        }
    }
    cout<<ans<<endl;
	return 0;
}
Chủ đề: Đồ thị, Kruskal Mức độ: ,

QBBISHOP – spoj

October 31, 2016 by Leave a Comment

Đề bài: [xem đề bài]

covua-yeulaptrinh.pw

Thuật toán:

  • BFS từ ô (s.x,s.y)
  • Mỗi lần BFS lấy ra ô (u,v) đi theo 4 đường chéo có dạng (u-x,v-x) , (u-x,v+x) , (u+x,v-x) , (u+x,v+x).
  • Đừng quên là không thể đi đến ô đang có cờ.

Code: [xem code]

const   fi='';
        fo='';
        maxn=200;
        dx:array[1..4] of integer =(1,-1,1,-1);
        dy:array[1..4] of integer =(1,1,-1,-1);
type    point=record
                x,y:integer;
                end;
var     free:array[0..maxn+1,0..maxn+1] of boolean;
        bac:array[0..maxn+1,0..maxn+1] of integer;
        q:array[1..maxn*maxn] of point;
        n,m,i,j:integer;
        s,f:point;
        dau,cuoi,res:longint;
procedure nhap;
var     x,y:integer;
begin
    assign(input,fi);reset(input);
    readln(n,m,s.x,s.y,f.x,f.y);
    fillchar(free,sizeof(free),false);
    for i:=1 to n do
        for j:=1 to n do free[i,j]:=true;
    for i:=1 to m do
        begin
            readln(x,y);
            free[x,y]:=false;
        end;
end;
procedure init;
begin
 
end;
procedure push(x,y:integer);
begin
    inc(cuoi);
    q[cuoi].x:=x;
    q[cuoi].y:=y;
end;
procedure bfs;
var     u,v:point;
begin
    dau:=1;cuoi:=1;
    q[1].x:=s.x;q[1].y:=s.y;
    while dau<=cuoi do
        begin
            u:=q[dau]; inc(dau);
            for i:=1 to 4 do
                for j:=1 to n do
                        begin
                            v.x:=dx[i]*j+u.x;
                            v.y:=dy[i]*j+u.y;
                            if (v.x=f.x) and (v.y=f.y) then
                                begin
                                        res:=bac[u.x,u.y]+1;
                                        exit;
                                end;
                            if (v.x>=1) and (v.y>=1) and (v.x<=n) and (v.y<=n) and (free[v.x,v.y])  then
                                begin
                                   bac[v.x,v.y]:=bac[u.x,u.y] +1;
                                   free[v.x,v.y]:=false;
                                   push(v.x,v.y);
                                end else break;
                        end;
        end;
    res:=-1;exit;
end;
procedure xuly;
begin
    if (s.x+s.y) mod 2<>(f.x+f.y) mod 2 then begin res:=-1; exit; end;
    bfs;
 
end;
procedure inkq;
begin
    assign(output,fo);rewrite(Output);
 
    writeln(res);
 
    close(output);
end;
begin
    nhap;
    init;
    xuly;
    inkq;
end.
Chủ đề: BFS Mức độ:

ROBOCON – vn.spoj.com

September 27, 2016 by Leave a Comment

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

Thuật toán:

  • Bạn loang con robot 1 trong khi loang robot 1 bạn cũng đồng thời loang robot 2. Ta phải suy luận ra một số trường hợp để mà dừng loang
  • Bạn có thể đọc code của mình để hiểu thêm. Mình viết rất dễ hiểu, bạn đọc có thể hiểu ngay

Code:

const
  fi='';
  fo='';
  maxn=501;
  maxq=20*maxn*maxn;
  oo=trunc(1e9);
type
  point = record
    x,y,d : longint;
  end;
var
  dau1,cuoi1,dau2,cuoi2,i,j,n,m : longint;
  a : array[0..maxn,0..maxn] of boolean;
  q1,q2 : array[1..maxq] of point;
  d1,d2 : array[1..maxn,1..maxn] of longint;
  nowd,res : longint;
  kt : boolean;
 
procedure enter;
var u,v : longint;
begin
  assign(input,fi);reset(input);
  fillchar(a , sizeof(a) , false);
  readln(n,m);
  for i:=1 to n do for j:=1 to n do a[i,j] := true;
  for i:=1 to m do
    begin
      read(u,v);
      a[u,v] := false;
    end;
end;
procedure push1(x,y,z : longint);
begin
  inc(cuoi1);
  q1[cuoi1].x := x;
  q1[cuoi1].y := y;
  q1[cuoi1].d := z;
  d1[x,y] := z;
  if d2[x,y]=z then
    begin
      res := z;
      kt:=true;
      exit;
    end;
end;
procedure push2(x,y,z : longint);
begin
  inc(cuoi2);
  q2[cuoi2].x := x;
  q2[cuoi2].y := y;
  q2[cuoi2].d := z;
  d2[x,y] := z;
end;
procedure bfs2(dd : longint);
var u : point;
    i,j : longint;
begin
  while dau2<=cuoi2 do
    begin
      u := q2[dau2]; inc(dau2);
      if u.d>dd then begin dec(dau2); exit; end;
      i:=u.x;j:=u.y;
      if a[i,j-1] and (d2[i,j-1]<>dd+1) then push2(i,j-1,dd+1);
      if a[i+1,j] and (d2[i+1,j]<>dd+1) then push2(i+1,j,dd+1);
      if a[i+1,j-1] and (d2[i+1,j-1]<>dd+1) then push2(i+1,j-1,dd+1);
    end;
end;
procedure bfs1;
var u : point;
    i,j : longint;
begin
  fillchar(d1,sizeof(d1),255);
  fillchar(d2,sizeof(d2),255);
  kt := false;
  dau1 :=1; cuoi1 := 0;
  dau2 := 1; cuoi2 := 0;
  push1(1,1,0); push2(1,n,0);
  nowd := 0;
  while dau1<=cuoi1 do
    begin
      if kt then break;
      u := q1[dau1]; inc(dau1);
      if u.d=nowd then
        begin
          bfs2(nowd);
          inc(nowd);
        end;
      i := u.x ; j:=u.y;
      if a[i+1,j] and (d1[i+1,j]<>u.d+1) then push1(i+1,j,u.d+1);
      if a[i,j+1] and (d1[i,j+1]<>u.d+1) then push1(i,j+1,u.d+1);
      if a[i+1,j+1] and (d1[i+1,j+1]<>u.d+1) then push1(i+1,j+1,u.d+1);
    end;
end;
procedure process;
begin
  res := oo;
  bfs1;
end;
procedure print;
begin
  assign(output,fo);rewrite(output);
  writeln(res);
  close(output);
end;
begin
  enter;
  process;
  print;
end.
Chủ đề: BFS Mức độ: ,

CENTRE28 – SPOJ

June 11, 2016 by Leave a Comment

Đề 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;
}
Chủ đề: Dijkstra, Heap Mức độ: ,

QBROBOT – SPOJ

June 10, 2016 by Leave a Comment

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

Thuật toán:

  • Tìm đường đi ngắn nhất bằng Dijkstra
  • Chắt nhị phân giá trị w
  • Với mỗi giá trị w kiểm tra xem có thỏa mãn không

Code:

#include <iostream>
#include <cmath>
#include <fstream>
#include <bits/stdc++.h>
#define MAXN 502
#define MAXM 30002
#define VC 2000000000
int n, m, dau[MAXM], cuoi[MAXM], t[MAXM], c[MAXM], x[MAXN];
long tro[MAXN];
int ke[2*MAXM];
int qn, q[MAXN], vt[MAXN];
long kc[MAXN], nl[MAXN], ds;
int prev[MAXN];
int tt[MAXN], sl=0;
using namespace std;
int doc()
{
    int i;
    cin >> n;
    for (i=1; i<=n; i++) cin >> x[i];
    cin >> m;
    for (i=1; i<=m; i++) cin >> dau[i] >> cuoi[i] >> t[i] >> c[i];
}
 
// Ham dung do thi
int dungdt()
{
    long u,v;
    int i;
    for (i=1; i<=m; i++) {tro[dau[i]]++; tro[cuoi[i]]++;}
    for (v=0,i=1; i<=n; i++) {u=tro[i]; tro[i]=v+1; v+=u;}
    tro[n+1]=v+1;
    for (i=1; i<=m; i++) {ke[tro[dau[i]]++]=i; ke[tro[cuoi[i]]++]=i;}
    for (i=n; i>=2; i--) tro[i]=tro[i-1]; tro[1]=1;
}
 
// Cac ham quan ly hang doi uu tien
int up(int k)
{
    int v=q[k];
    while (kc[q[k/2]]>kc[v])
    {
        q[k]=q[k/2];
        vt[q[k]]=k;
        k/=2;
    }
    q[k]=v;
    vt[q[k]]=k;
}
int down(int k)
{
    int v=q[k];
    while (2*k<=qn)
    {
        int l=2*k;
        if ((l<qn) && (kc[q[l+1]]<kc[q[l]])) l++;
        if (kc[q[l]]>=kc[v]) break;
        q[k]=q[l];
        vt[q[k]]=k;
        k=l;
    }
    q[k]=v;
    vt[q[k]]=k;
}
int initq() {qn=0; vt[0]=0; kc[0]=-1;}
int put(int u) {q[++qn]=u; vt[u]=qn; up(qn);}
int get() {int kq=q[1]; q[1]=q[qn--]; vt[q[1]]=1; down(1); return kq;}
int update(int u) {int k=vt[u]; up(k);}
int qempty() {return (qn==0);}
 
// Ham dijstra tim khoang cach ngan nhat
int dijstra()
{
    initq();
    kc[1]=0; prev[1]=-(n+1);
    put(1);
    while (!qempty())
    {
        int u=get(); prev[u]=-prev[u];
        tt[++sl]=u;
        for (long i=tro[u]; i<tro[u+1]; i++)
        {
            int v;
            if (dau[ke[i]]!=u) v=dau[ke[i]]; else v=cuoi[ke[i]];
            if ((prev[v]<0) && (kc[v]>kc[u]+t[ke[i]]))
            {
                kc[v]=kc[u]+t[ke[i]];
                prev[v]=-u;
                update(v);
            }
            if (prev[v]==0)
            {
                kc[v]=kc[u]+t[ke[i]];
                prev[v]=-u;
                put(v);
            }
        }
    }
    return 0;
}
 
 
// Ham kiem tra co di duoc hay khong
int diduoc(long w)
{
    long i,k,u,v,tg,cp,cl;
    for (i=1; i<=n; i++) nl[i]=-VC;
    nl[1]=w;
    for (k=1; k<=sl; k++)
    {
        u=tt[k];
        if (nl[u]>=0)
        for (i=tro[u]; i<tro[u+1]; i++)
        {
            if (dau[ke[i]]!=u) v=dau[ke[i]]; else v=cuoi[ke[i]];
            tg=t[ke[i]]; cp=c[ke[i]];
            if ((kc[v]==kc[u]+tg) && (nl[u]>=cp))
            {
                cl=(x[v]==1) ? w : nl[u]-cp;
                if (cl>nl[v]) nl[v]=cl;
            }
        }
    }
    return (nl[n]>=0);
}
 
// Ham tim chi phi be nhat (dua vao theo tim kiem nhi phan)
int solve()
{
    long first=0, last=1, lim;
    while (!diduoc(last)) {first=last; last*=2;}
    while (last-first>1)
    {
        lim=(last+first)/2;
        if (diduoc(lim)) last=lim; else first=lim;
    }
    ds=last;
}
 
// Ham in ket qua
int viet()
{
    cout << ds;
    //<< // '\n';
    /*out << kc[n] << '\n';
    for (long i=tro[1]; i<tro[2]; i++)
    {
        int v;
        if (dau[ke[i]]!=1) v=dau[ke[i]]; else v=cuoi[ke[i]];
        if (v==n) out << t[ke[i]] << ' ' << c[ke[i]] << '\n';
    } */
    }
 
// CHUONG TRINH CHINH
int main()
{
    doc();
    dungdt();
    dijstra();
    solve();
    viet();
}
Chủ đề: Dijkstra, SPOJ, Tìm kiếm nhị phân Mức độ: ,

DHFRBUS – SPOJ

April 18, 2016 by Leave a Comment

Đề 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.
Chủ đề: Dijkstra, SPOJ, Thuật toán Mức độ: , , , ,