PVOI14_3 – spoj

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

VDANGER – spoj

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

Thuật toán:

  • Gợi ý là sử dụng thuật toán Floyd rồi cộng lại ra kết quả bài toán

Code:

VAR 
  a :array[1..10000] of byte;
  c :array[1..100,1..100] of longint;
  t :array[1..100,1..100] of byte;
  n :byte;
  m :word;
 
procedure Enter;
  var i,j :word;
  begin
    readln(n,m);
    for i:=1 to m do readln(a[i]);
    for i:=1 to n do
      begin
        for j:=1 to n do
          begin 
            read(c[i,j]); t[i,j]:=j; 
          end;
        readln;
      end;
  end;
 
procedure Optimize;
  var i,j,k :byte;
  begin
    for k:=1 to n do
    for i:=1 to n do
    for j:=1 to n do
    if (c[i,j]>c[i,k]+c[k,j]) then
      begin
        c[i,j]:=c[i,k]+c[k,j];
        t[i,j]:=t[i,k];
      end;
  end;
 
procedure Quit;
  var 
    i :word;
    sum :longint;
  begin
    sum:=0;
    if (a[1]<>1) then sum:=sum+c[1,a[1]];
    for i:=2 to m do sum:=sum+c[a[i-1],a[i]];
    if (a[m]<>n) then sum:=sum+c[a[m],n];
    write(sum);
  end;
 
BEGIN
  assign(input,''); reset(input);
  assign(output,''); rewrite(output);
  Enter; 
  Optimize; 
  Quit;
  close(input); close(output);
END.

DHSERV – SPOJ

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

Thuật toán:

  • Bài này thuần sử dụng thuật toán Floyd. Các bạn có thể tham khảo code bên dưới để hiểu thêm.

Code:

const
  fi='';//hserv.inp';
  fo='';//dhserv.out';
  maxn=500;
  oo=trunc(1e18);
var
  a : array[1..maxn,1..maxn] of int64;
  d : array[1..maxn,1..maxn] of int64;
  i,j,n,m,k : longint;
procedure enter;
  var u,v,w : longint;
  begin
    assign(input,fi);reset(input);
    readln(n,m,k);
    for i:=1 to n do
      for j:=1 to n do
        if i<>j then
          begin
            d[i,j] := oo;
            a[i,j] := oo;
          end else
          begin
            d[i,j] := 0;
            a[i,j] := 0;
          end;
    for i:=1 to m do
      begin
        read(u,v,w);
        a[u,v] := w;
        d[u,v] := w;
      end;
  end;
procedure process;
  var tg,kieu,u,v,kk : longint;
  begin
    assign(output,fo);rewrite(output);
    for kk:=1 to k do
      begin
        read(kieu);
        if kieu=1 then
          begin
            read(tg);
            for u:=1 to n do
              for v:=1 to n do
                if d[u,v] > d[u,tg] + d[tg,v] then
                  begin
                    d[u,v] := d[u,tg] + d[tg,v];
                  end;
          end;
        if kieu=2 then
          begin
            read(u,v);
            if d[u,v]=oo then writeln(-1) else 
            writeln(d[u,v]);
          end;
      end;
      close(output);
  end;
begin
  enter;
  process;
end.