Đề 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. |
BÌNH LUẬN MỚI