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 
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 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 q;
vector 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

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 
#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
#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 > 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 

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 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>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<

{$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
#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 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<
Chủ đề: Đồ thị, Kruskal Mức độ: ,