PVOI14_3 – spoj

Đề bài:

---

• http://vn.spoj.com/problems/PVOI14_3/

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:

---

• Pascal: ideone
• C++: ideone

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