SAFENET2 – spoj

Đề bài:

Thuật toán:

  • (đang cập nhập)

Code:

uses math;
const
  fi='';//safenet.inp';
  fo='';//safenet.out';
  maxn=50000;
  maxm=200000;
  oo=trunc(1e9);
type
  Tedge = record
     x,y  : longint;
     end;
var
  link,head,ke : array[-maxm..maxm] of longint;
  i,j,n,m,u,v,ans,top,count,dem : longint;
  num,low : array[1..maxn] of longint;
  st : array[1..maxm] of Tedge;
  free : array[-maxm..maxm] of boolean;
  pa : array[1..maxn] of longint;
procedure push(x,y : longint);
  begin
    inc(top);
    st[top].x := x;
    st[top].y := y;
  end;
procedure pop ( var x,y : longint);
  begin
    x := st[top].x;
    y := st[top].y;
    dec(top);
  end;
procedure dfs(u : longint);
  var i,v,x,y : longint;
  begin
    inc(count);
    num[u] := count;
    low[u] := oo;
    if count = 1 then
      if head[u] = 0 then
        ans := max(ans,1);
    i := head[u];
    while i <> 0 do
      begin
          v := ke[i];
          if v <> pa[u] then
          if num[v] = 0 then
            begin
              pa[v] := u;
              push(u,v);
              dfs(v);
              low[u] := min(low[u],low[v]);
              if low[v] >= num[u] then
                begin
                  dem := 0;
                  repeat
                    pop(x,y);
                    dem := dem + 1;
                  until (X=U) AND (Y=V);
                  ans := max(ans,dem+1);
                end;
            end
            else
            begin
              low[u] := min(low[u],num[v]);
            end;
        i := link[i];
      end;
  end;
procedure add(i,u,v : longint);
  begin
    link[i] := head[u];
    head[u] := i;
    ke[i] := v;
  end;
procedure main;
var i  :  longint;
begin
  assign(input,fi);reset(input);
  assign(output,fo);rewrite(output);
  read(n,m);
  for i := 1to m do
    begin
      read(u,v);
      add(i,u,v);
      add(-i,v,u);
    end;
  fillchar(free,sizeof(free),true);
  for i := 1 to n do
    if num[i] = 0 then
      begin
        count := 0;
        dfs(i);
      end;
  writeln(ans);
  close(input);close(output);
end;
begin
  main;
end.

PWALK – spoj

Đề bài:

Thuật toán:

  • DFS để thiết lập thứ tự cha/con rồi với mỗi truy vấn chỉ cần đi ngược lên đến khi gặp cha chung thì dừng.

Code:

#include <iostream>
#include <vector>
using namespace std;
 
struct pack { int u, c; };
typedef vector<vector<pack>> dsk;
 
int d[1001], bac[1001], cha[1001];
 
void dfs(int u, const dsk &ke) {
    for (pack p: ke[u]) if (p.u != cha[u]) {
        int v = p.u, c = p.c;
        d[v] = c;
        cha[v] = u;
        bac[v] = bac[u] + 1;
        dfs(v, ke);
    }
}
 
int solve(int u, int v) {
#define up(u) sum += d[u], u = cha[u]
    int sum = 0;
    while (bac[u] > bac[v]) up(u);
    while (bac[v] > bac[u]) up(v);
    while (u != v) up(u), up(v);
    return sum;
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int n, q; cin >> n >> q;
    dsk ke(n+1);
    for (int i=1; i<n; i++) {
        int u, v, c;
        cin >> u >> v >> c;
        ke[u].push_back({v, c});
        ke[v].push_back({u, c});
    }
    dfs(1, ke);
    while (q--) {
        int u, v; cin >> u >> v;
        cout << solve(u, v) << '\n';
    }
    return 0;
}

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.

BCISLAND – ptit

Đề bài:


Thuật toán:


- Bài này chia ra làm các bước như sau:
+ B1: Tìm độ cao lớn nhất so với mặt nước biển. (Hmax)
+ B2: Với độ cao tăng thêm: extra = 1-&gt;Hmax ta sẽ loang bắt đầu từ các cạnh là biển loang vào những nới có độ (độ cao &lt;= extra).
VD: có bản đồ:
5 5 5 5 7
4 1 1 1 4
4 1 2 1 3
7 1 0 0 4
7 3 4 4 4
với extra=1 ta thu được check[][]:
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

+B3: Đếm số thành phần liên thông tại check[][] với các check[][]==0 bằng DFS;
Số thành phần liên thông &gt; 1 thì tại độ cao extra đó đảo bị chia cắt;
VD: ở bản đồ trên tại extra = 3 ta có check[][]:
0 0 0 0 0
0 1 1 1 0
0 1 0 1 1
0 1 1 1 0
0 1 0 0 0

Code:


#include <iostream>
using namespace std;
 
int n, m;
int seawater[102][102];
int Hmax=0;
void read ()
{
	for (int i=1; i<=n; i++)
	{
		for (int j=1; j<=m; j++)
		{
			cin>>seawater[i][j];
			if (seawater[i][j]>Hmax) Hmax=seawater[i][j];
		}
	}
}
 
int check[102][102];
int check_connect[102][102];
void init ()
{
	for (int i=1; i<=n; i++)
	{
		for (int j=1; j<=m; j++)
		{
			check[i][j]=0;
			check_connect[i][j]=0;
		}
	}
}
 
int extra;
int x_ar[]={+1, +0, -1, +0};
int y_ar[]={+0, -1, +0, +1};
void loang (int i, int j)
{
	check[i][j]=1;
	for (int k=0; k<4; k++)
	{
		int X=j+x_ar[k];
		int Y=i+y_ar[k];
		if (X>=1 && X<=m && Y>=1 && Y<=n)
		{
			if (check[Y][X]==0 && seawater[Y][X]<=extra) loang (Y, X);
		}
	}
}
 
void DFS (int i, int j)
{
	check_connect[i][j]=1;
	for (int k=0; k<4; k++)
	{
		int X=j+x_ar[k];
		int Y=i+y_ar[k];
		if (X>=1 && X<=m && Y>=1 && Y<=n)
		{
			if (check_connect[Y][X]==0 && check[Y][X]==check[i][j]) DFS (Y, X);
		}
	}
}
 
int main ()
{
	int t=0;
	while (1)
	{
		cin>>n>>m;
		if (n==0 && m==0) break;
		t++;
		read ();
		int kt=0;
		for (int k=0; k<=Hmax; k++)
		{
			extra=k;
			init ();
			for (int i=1; i<=n; i++)
			{
				for (int j=1; j<=m; j++)
				{
					if ((i==1 || i==n || j==1 || j==m) && seawater[i][j]<=k && check[i][j]==0) loang (i, j);
				}
			}
			//dem lien thong?
			int count_connect=0;
			for (int i=1; i<=n; i++)
			{
				for (int j=1; j<=m; j++)
				{
					if (check_connect[i][j]==0 && check[i][j]==0)
					{
						count_connect++;
						DFS (i, j);
					}
				}
			}
			if (count_connect>1)
			{
				kt=1;
				break;
			}
		}
		if (kt==1) cout<<"Case "<<t<<": Island splits when ocean rises "<<extra<<" feet."<<endl;
		else cout<<"Case "<<t<<": Island never splits."<<endl;
	}
	return 0;
}

UPGRANET – spoj

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

ADS – spoj

Đề bài:

Thuật toán:

  • Kết quả là: m – n + số thành phần liên thông
  • Chứng minh
    1. Nếu 1 thành phần liên thông thì cách xếp hành trình tối ưu nhất là xếp hành trình của mỗi nhân viên có một con đường riêng còn lại giống nhau (“Hành trình phân công cho mỗi nhân viên phải có ít nhất một đoạn đường chưa có nhân viên nào khác đi tiếp thị.”) Giả sử có 1 cây khung n-1 cạnh =>  còn lại m-n+1 cạnh thừa => xếp nhiều nhất thêm m-n+1 hành trình.
    2. Nếu có nhiều thành phần liên thông thì tương tự. Kết quả là: SUM(m[i]-n[i]+1) = m – n +1 với i=1..n, m[i] là số cạnh tplt i, n[i] số đỉnh tplt i.

Code:

const   fi='';
        fo='';
        maxn=2000;
var     a:array[1..maxn,1..maxn] of boolean;
        cx:array[1..maxn] of boolean;
        i,j,n,m,res,x,y,dem:integer;
procedure dfs(u:integer);
var     v:integer;
begin
    cx[u]:=true;
    for v:=1 to n do
        if not cx[v] then
          if a[u,v] then
                dfs(v);
end;
begin
    assign(input,fi);reset(input);
    assign(output,fo);rewrite(output);
 
    readln(n,m);
    for i:=1 to m do
        begin
            readln(x,y);
            a[x,y]:=true;
            a[y,x]:=true;
        end;
 
    for i:=1 to n do
        if not cx[i] then
                begin
                    inc(dem);
                    dfs(i);
                end;
 
    res:=m-n+dem;
 
    writeln(res);
 
    close(input);close(output);
end.

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.