if (color[v,j]=FREE)
then
begin
if (G[v,j]=B) and (LabC=1)
then begin OutRes; halt; end;
if G[v,j]=C then LabC:=1;
color[v,j]:=DONE; inc(ks); sled[ks]:=G[v,j];
DFS(G[v,j]);
color[v,j]:=FREE; sled[ks]:=0; dec(ks);
if G[v,j]=C then LabC:=0;
end;
end;
begin
assign(input,'path.in'); reset(input);
assign(output,'path.out'); rewrite(output);
read(N,M);
for i:=1 to M do
begin
read(x,y); inc(kG[x]); G[x,kG[x]]:=y; color[x,kG[x]]:=FREE;
end;
read(A,B,C);
LabC:=0;
DFS(A);
writeln(-1);
close(input); close(output);
end.
(Автор - Котов В.М.)
Республиканская олимпиада по информатике 1998г
Даны декартовы координаты N перекрестков города, которые пронумерованы от 1 до N. На каждом перекрестке имеется светофор. Некоторые из перекрестков соединены дорогами с двухсторонним (правосторонним) движением, которые пересекаются только на перекрестках. Для каждой дороги известно время, которое требуется для проезда по ней от одного перекрестка до другого.
Необходимо проехать от перекрестка с номером А до перекрестка с номером В за минимальное время.
Время проезда зависит от набора проезжаемых дорог и от времени ожидания на перекрестках. Так, если вы подъехали от перекрестка X к перекрестку C по дороге Х->C и хотите ехать дальше по дороге C->У, то время ожидания на перекрестке C эависит от того, поворачиваете ли вы налево или нет. Если вы поворачиваете налево, то время ожидания равно D*К, где D равно количеству дорог, пересекающихся на перекрестке C, а К - некоторая константа. Если вы не поворачиваете налево, то время ожидания равно нулю.
Написать программу, которая определяет самый быстрый маршрут.
Спецификация входных данных.
Входные данные находятся в текстовом файле с именем PER.IN и имеют следующую структуру:
- в первой строке находится число N (натуральное, <=1000);
- во второй строке - количество дорог M (натуральное, <=1000);
- в третьей строке - константа K (натуральное число, <=1000);
- в каждой из N следующих стpок находится паpа чисел х и у, разделенных пробелом, где x, y - кооpдинаты перекрестка (целые числа, не пpевышающие по модулю 1000);
- в каждой из M следующих строк находится 3 числа p, r, t, разделенные пробелом, где p и r - номера перекрестков, которые соединяет дорога, а t (натуральное, <=1000) - время проезда по ней;
- в последней строке находятся номера начального А и конечного В перекрестков.
Спецификация выходных данных.
Выходные данные должны быть записаны в текстовый файл с именем PER.OUT и иметь следующий формат:
- в первой строке находится натуральное число T - время проезда по самому быстрому маршруту;
- в каждой из следующих строк находится одно число - номер очередного перекрестка в маршруте (начиная с перекрестка с номером А и кончая В).
Кратко идея решения может быть изложена следующим образом.
Алгоритм Дейкстры напрямую не применим, поскольку:
а) оптимальное решение в следующей вершине не является суммой оптимального решения для предыдущей вершины и веса текущего ребра
б) вес текущего ребра - непостоянная величина, зависящая от того, каким поворотом мы вышли из вершины.
Поэтому предлагается решение поиском в глубину. При этом разрешается использовать каждую вершину столько раз, сколько у нее есть ребер. Отсекаются решения хуже текущего оптимального.
Можно еще ускорить решение, если обеспечивать перебор, начиная с правых поворотов (отсечения работали бы более эффективно).
Замечание:
В тексте задачи явно не указано, но авторы оригинальных тестов к задаче полагали, что поворот на 180 градусов - это левый поворот (как в армии: поворот на 180 градусов - "через левое плечо").
Рассмотрим решение более подробно:
Ввод исходных данных осуществляется следующим образом:
read(N,M,K);
for i:=1 to N do readln(x[i],y[i]);
for i:=1 to N do begin kG[i]:=0; D[i]:=0; end;
for i:=1 to M do
begin
readln(p,r,t); inc(kG[p]); inc(kG[r]);
G[p,kG[p],1]:=r; G[p,kG[p],2]:=t; inc(D[p]);
G[r,kG[r],1]:=p; G[r,kG[r],2]:=t; Inc(D[r]);
end;
readln(vA,vB);
Здесь kG[i] - количество дуг из вершины i
G[i,j,1] - вершина, с которой соединена вершина i дугой с номером j в списке всех дуг из вершины i.
G[i,j,2] - время проезда от вершины i до вершины, с которой она соединена дугой j в списке всех дуг из вершины i.
D[i] - количество дорог, пересекающихся на перекрестке i (то есть суммарное количество дуг, исходящих из вершины i и входящик в нее),
vA и vB указывают, откуда и куда нужно добираться.
Поскольку по условиям задачи дороги двусторонние, то, для каждой введенной дороги, мы добавляем в граф две дуги.
Основной алгоритм выглядит следующим образом:
for i:=1 to N do
begin
for j:=1 to kG[i] do Color[i,j]:=WHITE; { вседугисвободны }
Time[i]:=maxlongint; { время маршрута до I - максимально }
end;
OptT:=Maxlongint; { Оптимальное время - максимально}
Sled[1]:=vA; { Заносим в маршрут вершину vA}
kv:=1; { Количество вершин в маршруте = 1}
Time[vA]:=0; { Оптимальное время до вершины vA =0}
DFS(vA); { Поиск в глубину от вершины vA }
вывод ответа
Рекурсивная процедура DFS(i) обеспечивает выполнение следующей работы:
Procedure DFS(i)
begin
for j:=1 to kG[i] do
if G[i,j,1]<>vB
then
begin
if color[i,j]=FREE
then
begin
продолжение пути с вызовом DFS
end
end
else
begin
сравнение пути с текущим оптимальным
end;
end;
Если текущая вершина - конечная (vB), то делаем " ... сравнение пути с оптимальным"
Иначе проверяем, если текущая дуга еще не использовась (color[i,j]=FREE) то делаем "... продолжение пути с вызовом DFS".
При этом, перед входом в DFS помечаем дугу как использованную (color[i,j]:=DONE), а после выхода - как вновь свободную (color[i,j]:=FREE);
"... продолжение пути с вызовом DFS" включает в себя следующие операторы:
inc(kv); sled[kv]:=G[i,j,1]; { помещаем в путь новую вершину }
NewTime:=Time[i]+G[i,j,2]+CountTime; {вычисляемновоевремя}
if NewTime<OptT {если новое время меньше оптимального}
then {то продолжаем,иначе - отсекаем}
begin
color[i,j]:=DONE; { Помечаем - ребро использовано }
RetTime:=Time[G[i,j,1]]; { Сохраняем старое время }
Time[G[i,j,1]]:=NewTime; { Устанавливаем новое время }
DFS(G[i,j,1]); { Вызываем поиск от G[i,j,1] }
Time[G[i,j,1]]:=RetTime; { Восстанавливаем старое время }
color[i,j]:=FREE; { Помечаем - ребро свободно }
end;
Sled[kv]:=0; dec(kv); { Удаляем вершину из пути }
Для вычисления нового времени здесь используется функция CounTime с параметром kv - номер последней вершины в стеке.Эта функция делает следующее: Восстанавливает номера вершин, прохода через перекресток "из i1 через i2 в i3":
if kv=2 then begin CountTime:=0; exit; end;
i1 := sled[kv-2];
i2 := sled[kv-1];
i3 := sled[kv];
if i3=i1 then begin CountTime:=K*D[i2]; exit; end;
Попутно, выясняется
а) если вершин в пути всего 2, то есть не было никакого поворота - это шаг из начальной вершины и CountTime=0.
б) если i1=i3 то это поворот на 180 градусов и авторы задачи считают, что это тоже левый поворот, CountTime=K*D[i2]; где, K - коэффициент который вводится, i2 - перекресток, D[i2] - количество дорог, входящих в этот перекресток.
Затем из массивов координат перекрестков выбираются координаты текущих перекрестков: (x1,y1) (откуда); (x2,y2) (через какой); (x3,y3) (куда).
x1 := x[i1]; x2:=x[i2]; x3:=x[i3];
y1 := y[i1]; y2:=y[i2]; y3:=y[i3];
Вычисляется уравнение прямой по точкам (x1,y1) и (x2,y2)
A := y2-y1;
B := x1-x2;
C := y1*(x2-x1)-x1*(y2-y1);
Подстановкой координат (x3,y3) в уравнение прямой Ax+By+C=0, построенной по первым двум точкам (x1,y1) и (x2,y2) и с учетом крайних случаев, когда прямая параллельна осям координат, вычисляем, был ли поворот левым или правым и соответственно устанавливаем значение функции CountTime.
Left := (((x2>x1) and ((A*x3+B*y3+C)<0))) or
(((x2<x1) and ((A*x3+B*y3+C)<0))) or
(((y2=y1) and (x1>x2) and (y3<y1))) or
(((y2=y1) and (x1<x2) and (y3>y1))) or
(((x2=x1) and (y1>y2) and (x3>x1))) or
(((x2=x1) and (y1<y2) and (x3<x1))) ;
if Left then CountTime:=K*D[i2]
else CountTime:=0;
"Сравнение пути с оптимальным" выполняется следующим образом:
inc(kv); sled[kv]:=G[i,j,1];
T := Time[i]+G[i,j,2] + CountTime;
if T < OptT
then begin
OptT:=T;
OptKv:=kv; OptSled:=Sled;
end;
Sled[kv]:=0; dec(kv);
Таким образом, оптимальное время хранится в переменной OptT а оптимальный путь храниться в массиве OptSled с количеством элементов OptKv. И потому, вывод результатов выглядит так:
writeln(OptT);
fori:=1 toOptKvdowriteln(OptSled[i]);
Полный текст программы приводится ниже
program by98d2s2;
Const
FREE = 1;
DONE = 2;
Type
int1000 = 0..1000;
int3 = 1..3;
var
G : array[1..1000,1..10,1..2] of int1000;
Time,D : array[1..1000] of longint;
x,y,kG,Sled,OptSled,pred : array[1..1000] of int1000;
Color : array[1..100,1..10] of int3;
N,M,K,i,p,r,t,vA,vB,v,kv,OptKv,j : int1000;
OptT : longint;
function CountTime(i:int1000):longint;
var
Left : boolean;
i1,i2,i3 : int1000;
x1,x2,x3,y1,y2,y3,A,B,C : longint;
begin
if kv=2 then begin CountTime:=0; exit; end;
i1 := sled[kv-2];
i2 := sled[kv-1];
i3 := sled[kv];
if i3=i1 then begin CountTime:=K*D[i2]; exit; end;
x1 := x[i1]; x2:=x[i2]; x3:=x[i3];
y1 := y[i1]; y2:=y[i2]; y3:=y[i3];
A := y2-y1;
B := x1-x2;
C := y1*(x2-x1)-x1*(y2-y1);
Left := (((x2>x1) and ((A*x3+B*y3+C)<0))) or
(((x2<x1) and ((A*x3+B*y3+C)<0))) or
(((y2=y1) and (x1>x2) and (y3<y1))) or
(((y2=y1) and (x1<x2) and (y3>y1))) or
(((x2=x1) and (y1>y2) and (x3>x1))) or
(((x2=x1) and (y1<y2) and (x3<x1))) ;
if Left
then CountTime:=K*D[i2]
else CountTime:=0;
end;
Procedure DFS(i:int1000);
var
j : byte;
T : longint;
RetSled,RetPred,RetTime :longint;
begin
for j:=1 to kG[i] do
if G[i,j,1]<>vB
then
begin
if color[i,j]=FREE
then
begin
inc(kv); sled[kv]:=G[i,j,1];
NewTime:=Time[i]+G[i,j,2]+CountTime;
if NewTime<OptT
then
begin
color[i,j]:=DONE;
RetTime:=Time[G[i,j,1]];
Time[G[i,j,1]]:=NewTime;
DFS(G[i,j,1]);
Time[G[i,j,1]]:=RetTime;
color[i,j]:=FREE;
end;
Sled[kv]:=0; dec(kv);
end
end
else
begin
inc(kv); sled[kv]:=G[i,j,1];
T := Time[i]+G[i,j,2] + CountTime;
if T < OptT
then begin
OptT:=T;
OptKv:=kv; OptSled:=Sled;
end;
Sled[kv]:=0; dec(kv);
end;
end;
begin
assign(input,'PER.in'); reset(input);
assign(output,'PER.out'); rewrite(output);
read(N,M,K);
for i:=1 to N do readln(x[i],y[i]);
for i:=1 to N do begin kG[i]:=0; D[i]:=0; end;
for i:=1 to M do
begin
readln(p,r,t); inc(kG[p]); inc(kG[r]);
G[p,kG[p],1]:=r; G[p,kG[p],2]:=t; inc(D[p]);
G[r,kG[r],1]:=p; G[r,kG[r],2]:=t; Inc(D[r]);
end;
readln(vA,vB);
for i:=1 to N do
begin
for j:=1 to kG[i] do Color[i,j]:=FREE;
Time[i]:=maxlongint;
end;
Time[vA]:=0; kv:=1; Sled[1]:=vA; OptT:=Maxlongint;
DFS(vA);
writeln(OptT);
for i:=1 to OptKv do writeln(OptSled[i]);
close(input); close(output);
end.
(Автор - Котов В.М.)
Республиканская олимпиада по информатике 1995г
Скрудж Мак-Дак решил сделать прибор для управления самолетом. Как известно, положение штурвала зависит от состояния входных датчиков, но эта функция довольно сложна.
Его механик Винт Р. сделал устройство, вычисляющее эту функцию в несколько этапов с использование промежуточной памяти и вспомогательных функций. Для вычисления каждой из функций требуется, чтобы в ячейках памяти уже находились вычисленные параметры (которые являются значениями вычисленных функций), необходимые для ее вычисления. Вычисление функции без параметров может производится в любое время. После вычисления функции ячейки могут быть использованы повторно (хотя бы для записи результата вычисленной функции). Структура вызова функций такова, что каждая функция вычисляется не более одного раза и любой параметр используется не более одного раза. Любой параметр есть имя функции. Так как Скрудж не хочет тратить лишних денег на микросхемы, он поставил задачу минимизировать память прибора. По заданной структуре вызовов функций необходимо определить минимальный возможный размер памяти прибора и указать последовательность вычисления функций.