• Выгодней некуда
  PAYING
  
  Условие  Комментарии  Решение  Тестовые файлы  Оглавление

Описание
В стране N городов, в каждом из которых есть аэропорт. Авиакомпания, занимающаяся перевозкой грузов, имеет самолет и желает максимально выгодно его использовать. Для некоторых пар городов (А,В) известны время перелета из А в В и сумма выручки за доставку груза из города А в В

Задание
Напишите программу, которая по этим данным находит для самолета замкнутый путь, максимизирующий среднюю выручку за единицу времени. Считается, что самолет может вместить не более одного груза, а временем стоянки самолета в аэропорту следует пренебречь


Входные данные
В первой строке входного файла содержится число городов N (1≤N≤100) и число возможных прямых рейсов М. В каждой из следующих М строк записана четверка чисел (i,j,b_ij,c_ij), описывающая возможный рейс между городами i и j со временем перелета b_ij и выручкой c_ij. Время перелета и выручка - положительные вещественные числа

Выходные данные
В первой строке выходного файла должна содержаться максимальная средняя выручка за единицу времени, а во второй - замкнутый маршрут, заданный номерами своих вершин в порядке следования, на котором эта максимальная выручка достигается. Первая и последняя вершины маршрута должны совпадать. Входные данные будут таковы, что решение заведомо будет существовать


Например:

PAYING.IN
3 3
1 2 1.0 2.0
2 3 1.0 2.0
3 1 2.0 1.0

PAYING.OUT
1.25
1 2 3 1

Идеи
Поиск циклов отрицательного веса, двоичный поиск

Комментарии
Нужно найти такой цикл D, для которого средняя выручка за единицу времени

максимальна (сумма берется по всем ориентированным ребрам). Обозначим это максимальное значение через z*. Возьмем некоторое пробное значение z₀ и рассмотрим граф с модифицированными весами [Кристофидес 78, п.8.4]

c_ij' = c_ij - z₀b_ij

Используем алгоритм Флойда для нахождения циклов положительного с'-веса [Кристофидес 78, п.8.4]. Возможны три случая:

1. Существует цикл D положительного с'-веса. Это означает, что
   
   
   
   откуда z₀ < z(D) ≤ z* цикла
    

2. Существует цикл D с нулевым (но не положительным) c'-весом. В этом случае
   
   
   
   откуда z₀ = z(D) и z₀≤ z(E) для любого другого цикла Е. Следовательно, z₀ = z*
    

3. Все циклы графа имеют отрицательный с'-вес. Тогда для любого цикла D выполняются неравенства
   
   
   
   и z₀>z(D). Значит, z₀>z
    

Искать величину z* будем следующим образом. Сначала найдем для нее верхнюю (z₁) и нижнюю (z₂≥z₁/2) границы (подумайте, как это сделать!). Далее используем двоичный поиск, деля каждый раз отрезок [z₁,z₂] пробной точкой z₀=(z₁+z₂)/2 на две равные части и оставляя ту из них, на которой лежит z*. Необходимое при этом количество итераций пропорционально числу правильных значащих разрядов z*, которое мы хотим получить





Решение

{$A+,B-,D+,E-,F-,G-,I+,L+,N+,O-,P-,Q-,R-,S-,T-,V+,X+,Y+}
{$M 65520,0,655360}
 
program paying;
const
  nMax = 100;
  eps = 1e-8;
type
  tWeight = array[1..nMax, 1..nMax] of real;
var
  time, gain, graph : ^tWeight;
  mdl : array[1..nMax, 1..nMax] of byte;
  conn : array[1..nMax, 1..nMax] of boolean;
  N : integer;
 
procedure Init;
var
  i, left, right, M : integer;
begin
  assign(input, 'paying.in');
  reSet(input);
  assign(output, 'paying.out');
  reWrite(output);
 
  fillChar(conn, sizeOf(conn), 0);
  new(time); new(gain); new(graph);
 
  read(N, M);
  for i := 1 to M do begin
    read(left, right);
    read(time^[left, right], gain^[left, right]);
    conn[left, right] := true;
  end;
end;
 
function Eq(a, b : real) : boolean;
begin
  Eq := abs(a-b) < eps;
end;
 
procedure out(i, j : integer);
begin
  if mdl[i, j] = 0 then
    write(j, ' ')
  else begin
    out(i, mdl[i, j]);
    out(mdl[i, j], j);
  end;
end;
 
procedure print(k : integer; gain : real);
var
  i, j : integer;
begin
  writeLn(gain:0:8);
  write(k, ' ');
  out(k, mdl[k, k]); out(mdl[k, k], k);
end;
 
procedure solve;
var
  down, up, middle : real;
  i, j, k : integer;
  more0, finish : boolean;
label 1;
begin
  down := 0; up := 1e28;
  finish := false;
 
  repeat
    middle := (up+down)/2;
    for i := 1 to N do
      for j := 1 to N do
        if conn[i, j] then begin
          graph^[i, j] :=gain^[i, j]-middle*time^[i, j];
          if abs(graph^[i, j]) < eps then
            graph^[i, j] := 0;
        end
        else
          graph^[i, j] := -1e28;
    fillChar(mdl, sizeOf(mdl), 0);
 
    more0 := false;
    for k := 1 to n do
      for i := 1 to n do
        for j := 1 to n do begin
          if graph^[i, j] < graph^[i, k]+graph^[k, j] then begin
            graph^[i, j] := graph^[i, k]+graph^[k, j];
            if (k <> i) and (k <> j) then
              mdl[i, j] := k;
          end;
          if (i = j) and (graph^[i, j] > 0) then begin
            more0 := true;
            goto 1;
          end;
        end;
 
1:  if more0 then
      down := middle
    else begin
      i := 1;
      while (i <= N) and not Eq(graph^[i, i],0) do
        inc(i);
      if i <= N then begin
        print(i, middle);
        finish := true;
      end
      else
        up := middle;
    end;
  until finish;
end;
 
Begin
  Init;
  Solve;
End.

 

© Особенности национальных задач по информатике