--PAGE_BREAK--Входной файл: input2.txt Выходной файл: output2.txt
Формат ввода:
N
M
R11 T11 R12 T12
RM1 TM1 RM2 TM2
где N (2
M (M
Ri1 и Ri2 — номера комнат, в которых располагаются модули устройства i Ti1, Ti2 (Ti1,Ti2
Пример
4
5
1 5 3 2
1 1 2 1
2 5 3 5
4 4 3 2
3 5 4 5
Оптимальное время: 8.5 искомая последовательность: 2 3 4
Кратко алгоритм решения может быть изложен следующим образом.
Представив комнаты — вершинами, а пары устройств (с временами срабатывания) — взвешенными дугами, можем применить алгоритм Дейкстра для поиска кратчайшего пути от первой вершины до последней. Точнее, алгоритм Дейкстра построит кратчайшие пути от первой до всех остальных, но в данной задаче нас интересует только кратчайший путь от первой до последней. Нужно учитывать, что дуги существуют только в моменты, кратные временам срабатывания.
Рассмотрим решение более подробно.
Ввод исходных данных:
read(N,M); for I:=1 to N do kG[i]:=0;
for i:=1 to M do
begin
read(r1,t1,r2,t2);
nok:= (t1*t2) div Nod(t1,t2); {nok — наименьшее общее кратное}
{Nod-наибольший общий делитель}
{чисел t1 и t2}
inc(kG[r1]); G[r1,kg[r1]]:=r2; P[r1,kg[r1]]:=nok;
inc(kG[r2]); G[r2,kg[r2]]:=r1; P[r2,kg[r2]]:=nok;
end;
Исходный граф по условиям задачи неориентированный. Поэтому мы вводим обе дуги. При этом граф представляется в виде списка дуг смежных с текущей:
kG[i] — количество дуг из вершины i
G[i,j] — вершина, в которую из вершины i идет дуга под порядковым номером j
P[i,j] — вес дуги из вершины i вершину G[i,j]
Для вычисления nod используется функция, основанная на алгоритме Евклида:
function Nod (a,b:longint):longint;
begin
while (ab) do if a>b then a:=a-b else b:=b-a;
Nod:=a;
end;
Затем проводится подготовка к выполнению алгоритма Дейкстры:
for i:=1 to N do {Для всех вершин}
begin
Labl[i]:=FREE; {Помечаем как свободную}
divd[i]:=1; {Предок — первая}
d[i]:=maxlongint; {Расстояние до первой — маx}
end;
Labl[1]:=DONE; {Первая — обработана}
Pred[1]:=0; {Предок у первой — 0}
d[1]:=0; {Расстояние от первой до первой — 0}
for j:=1 to kG[1] do {Для всех дуг из первого ребра}
d[G[1,j]]:=P[1,j]+0.5; {Расстояние до первой вершины}
{равно весу ребра + 0.5}
Заметим, что в последней строке к весу ребер добавляется 0.5, поскольку по условиям задачи перемещение с помощью устройств из одной комнаты в другую занимает 0.5 единицы времени.
Далее идет основной цикл алгоритма Дейкстра
for i:=1 to N-1 do
begin
Поиск ближайшей к первой вершине из необработанных
Пересчет кратчайших расстояний через ближайшую вершину до вершин, смежных с ближайшей
end;
Первый этап — «Поиск ближайшей к первой вершине из необработанных»
MinD:=maxlongint; {MinD — max}
for j:=1 to N do {Для всех вершин}
if (Labl[j]=FREE) {если вершина свободна}
and (d[j]
{вершины меньше MinD}
then
begin
MinD:=d[j]; {Заносим это расстояние в MinD}
Bliz:=j {Вершину запоминаем как ближайшую}
end;
Labl[Bliz]:=DONE; {Найденную ближайшую помечаем}
{как обработанную}
Второй этап — «Пересчет кратчайших расстояний через ближайшую вершину до вершин, смежных с ближайшей»
for j:=1 to kG[Bliz] do {Для всех вершин смежных с ближайшей}
if (Labl[G[Bliz,j]]=FREE) {Если вершина еще не обрабатывалась}
then
begin
NewTime:=Calculat(d[bliz],P[bliz,j]); {Вычислитьрасстояниедонее}
{в терминах задачи-время}
{перемешения в нее}
if d[G[Bliz,j]]> NewTime +0.5 {Если новое время лучше}
then
begin
d[G[Bliz,j]]:= NewTime+0.5; {заносим его в массив D}
divd[G[Bliz,j]]:=Bliz; {указываем ближайшую как}
end; {предыдущую для текущей}
end;
При вычислении кратчайшего расстояния до текущей вершины через ближайшую (в терминах алгоритма Дейкстра) или времени перемещения из первой комнаты через ближашую в текущую (в терминах данной задачи) используется функция Calculat (T,Tnok):
function Calculat (T:single; Tnok:longint):longint;
var i: longint;
begin
TRes:=0;
while (T>TRes) do inc(TRes,Tnok);
Calculat:=TRes;
end;
Эта функция вычисляет время TRes (которое передается в вызывающую программу непосредственно через имя функции Calculat), ближайшее большее текущего времени T (T равно минимальному значению времени, которое потребовалось, что бы оптимальным образом добраться из первой вершины до ближайшей вершины) и кратное Tnok — периоду срабатывания пары устройств, связывающих комнаты Bliz (ближайшая) и G[Bliz,j] (текущая).
После выполнения алгоритма Дейкстра сформированы массивы
d[j] — кратчайшее расстояние от начальной вершины до вершины j
divd[j] — предок вершины j на оптимальном маршруте
По этой информации вывод результата осуществляется следующим образом:
tg:=N; i:=0; {Начиная с последней вершины}
while tg0 do {Пока не закончились предшествующие}
begin
inc(i); {Инкрементируем количество вершин в пути}
path[i]:=tg; {Заносим текущую в массив пути}
tg:=divd[tg]; {Переустанавливаем предыдущую}
end;
writeln('Оптимальное время: ',D[N]:0:1);
write('искомая последовательность:');
for j:=i-1 downto 1 do write(' ',path[j]);
Ниже приведен полный текст решения задачи.
{$R+,E+,N+}
program by96d1s2;
const
FREE=1;
DONE=2;
var
G: array[1..100,1..100] of byte;
P: array[1..100,1..100] of longint;
D: array[1..100] of single;
Labl,divd,kG: array[1..100] of byte;
path: array[1..100] of byte;
is,t1,t2,nok,Tres,NewTime: longint;
i,j,x,y,A,B,C,N,M,tg,Bliz: byte;
r1,r2: byte;
Yes: boolean;
MinD: single;
function Nod (a,b:longint):longint;
begin
while (ab) do
if a>b then a:=a-b else b:=b-a;
Nod:=a;
end;
function Calculat (T:single; Tnok:longint):longint;
var i: longint;
begin
TRes:=0;
while (T>TRes) do inc(Tres,Tnok);
Calculat:=TRes;
end;
begin
assign(input,'input2.txt'); reset(input);
assign(output,'output2.txt'); rewrite(output);
read(N,M);
for I:=1 to N do kG[i]:=0;
for i:=1 to M do
begin
read(r1,t1,r2,t2); nok:= (t1*t2) div Nod(t1,t2);
inc(kG[r1]); G[r1,kg[r1]]:=r2; P[r1,kg[r1]]:=nok;
inc(kG[r2]); G[r2,kg[r2]]:=r1; P[r2,kg[r2]]:=nok;
end;
for i:=1 to N do
begin
Labl[i]:=FREE; divd[i]:=1; d[i]:=maxlongint;
end;
Labl[1]:=DONE; Pred[1]:=0; d[1]:=0;
for j:=1 to kG[1] do d[G[1,j]]:=P[1,j]+0.5;
for i:=1 to N-1 do
begin
MinD:=maxlongint;
for j:=1 to N do
if (Labl[j]=FREE) and (d[j]
then begin MinD:=d[j]; Bliz:=j end;
Labl[Bliz]:=DONE;
for j:=1 to kG[Bliz] do
if (Labl[G[Bliz,j]]=FREE)
then begin
NewTime:=Calculat(d[bliz],P[bliz,j]);
if d[G[Bliz,j]]> NewTime +0.5
then
begin
d[G[Bliz,j]]:= NewTime+0.5;
divd[G[Bliz,j]]:=Bliz;
end;
end;
end;
tg:=N; i:=0;
while tg0 do
begin
inc(i); path[i]:=tg; tg:=divd[tg];
end;
writeln('Оптимальное время: ',D[N]:0:1);
write('искомая последовательность:');
for j:=i-1 downto 1 do write(' ',path[j]);
close(input); close(output);
nd.
2.3 Задача «Эх, дороги» (Автор — Котов В.М.) Республиканская олимпиада по информатике 1998г
Имеется N городов, которые пронумерованы от 1 до N (где N — натуральное, 1
Необходимо проехать из города А в город В, уплатив минимальную сумму за проезд. Стоимость проезда зависит от набора проезжаемых дорог и от способа проезда. Так, если вы подъехали к городу С по шоссейной (железной) дороге X->C и хотите ехать дальше по дороге C->Y того же типа, то вы должны уплатить только базовую стоимость проезда по дороге C->Y. Если тип дороги C->Y отличен от типа дороги Х->C, то вы должны уплатить базовую стоимость проезда по дороге C->Y плюс 10% от базовой стоимости проезда по этой дороге (страховой взнос). При выезде из города А страховой взнос платится всегда. Написать программу, которая находит самый дешевый маршрут проезда в виде последовательности городов и вычисляет стоимость проезда по этому маршруту.
Спецификация входных данных
Входные данные находятся в текстовом файле с именем TOUR.IN и имеют следующий формат:
— в первой строке находятся число N
— во второй строке — число M (количество дорог, натуральное M
— в каждой из следующих M строк находятся 4 числа x, y, t, p, разделенные пробелом, где x и y — номера городов, которые соединяет дорога, t — тип дороги (0 — шоссейная, 1 — железная), p — базовая стоимость проезда по ней (p — вещественное, 0
— в последней строке задается номера начального и конечного городов A и B.
Спецификация выходных данных
Выходные данные должны быть записаны в текстовый файл с именем TOUR.OUT и иметь следующий формат:
— в первой строке находится число S — стоимость проезда по самому дешевому маршруту, с точностью 2 знака после запятой;
— в каждой из последующих строк, кроме последней, находится два числа — номер очередного города в маршруте (начиная с города А) и тип дороги, по которой он выезжает из этого города (0 или 1), разделенные пробелом.
— в последней строке находится единственное число — номер города B.
Пример входного файла Пример выходного файла
TOUR.IN TOUR.OUT
3 22.0
2 1 0
1 2 0 10.00 2 1
2 3 1 10.00 3
1 3
Метод Дейкстра непосредственно (города — вершины) не может быть применен, поскольку оптимальный маршрут может потребовать заезда в один и тот же город два раза с целью меньше платить за страховой сбор на выезд из этого города.
Вводим 2*N вершин (где N — число городов). Для каждого города — две вершины. Первая, если мы въехали в город по дороге типа 0, вторая — если въехали в город по дороге типа 1.
Теперь можно применять непосредственно метод Дейкстра для вычисления кратчайших расстояний от заданного города A до всех введенных вершин.
Для конечного города B мы выбираем лучший из вариантов — заехать в B по дороге типа 0 или по дороге типа 1.
Метод Дейкстра позволяет сохранять предшественников вершин на оптимальном маршруте, что и используется для вывода полного ответа в заданном формате.
Рассмотрим решение задачи более подробно, основываясь на тексте программы — решения:
Ввод исходных данных осуществляется следующим образом:
read(N); {N — число городов}
read(M); {M — число дорог}
for x:=1 to N do {Устанавливаем}
for y:=1 to N do {между всеми городами}
for t:=0 to 1 do p[x,y,t]:=MAXR; {максимальную стоимость}
for i:=1 to M do {x — номер города «откуда»}
begin {y — номер города «куда»}
readln (x,y,t,p[x,y,t]); {t — тип дороги}
p[y,x,t]:=p[x,y,t]; {P[x,y,t] — стоимость}
end; {проезда от x к y по дороге типа t}
read(A,B); {Начальный и конечный пункты маршрута}
Подготовка к выполнению алгорима Дейкстра:
for i:=1 to N do {При выезде из города}
for t:=0 to 1 do {страховой взнос}
p[a,i,t]:=1.1*p[a,i,t]; {платится всегда}
for i:=1 to N do {Для всех городов}
begin {кратчайшие стоимости до первого}
D[i,0]:=P[a,i,0]; {по шоссейной дороге}
D[i,1]:=P[a,i,1]; {по железной дороге}
end;
for i:=1 to N do {Для всех городов}
begin
Labl[i,0]:=FREE; {Свободны}
Labl[i,1]:=FREE; {по обоим типам дорог}
divd[i,0]:=A; {Предыдущий город равен A}
divd[i,1]:=A; {для обоих типов дорог}
end;
Labl[A,0]:=DONE; {Начальный город обработан}
abl[A,1]:=DONE; {для обоих типов дорог}
divd[A,0]:=0; {Предыдущий у начального-0}
divd[A,1]:=0; {для обоих типов дорог}
Основная часть алгоритма Дейкстра представляет собой цикл по количеству вершин оставшихся необработанными
for i:=1 to 2*N-2 do
begin
Поиск ближайшей к первой вершине из необработанных
Пересчет наименьших стоимостей через ближайшую вершину до вершин, смежных с ближайшей end;
Первый этап — «Поиск ближайшей к первой вершине из необработанных»
MinD:=MaxR; {MinD — максимум}
for J:=1 to N do {Для всех городов}
for t:=0 to 1 do {Для дорог обоих типов}
if (Labl[j,t]=FREE) {Если въезд в город j по дороге типа t}
and {еще не обрабатывался и}
(minD>d[j,t]) {стоимость от города A до города j}
then {по дороге типа t меньше чем MinD, то}
begin
Bliz:=j; {Ближайшаяя — j}
bt:=t; {ее тип — bt}
MinD:=d[j,t] {минимальную стоимость в MinD}
end;
Labl[Bliz,bt]:=DONE; {Пометить как обработанную вершину}
{с минимальной стоимостью от города A}
{из еще необработанных вершин}
Второй этап — «Пересчет наименьших стоимостей через ближайшую вершину до вершин, смежных с ближайшей»
for j:=1 to N do {Для всех городов}
for t1:=0 to 1 do {Для дорог обоих типов}
if (Labl[j,t1]=FREE) {Если дорога до города j типа t необработана}
and (d[j,t1] {и стоимость до нее от вершины A}
> {больше чем}
d[Bliz,bt] + C(t1,bt)*P[Bliz,j,t1]) {стоимость через ближайшую}
then {то}
begin
d[j,t1]:=d[Bliz,bt]+C(t1,bt)*P[Bliz,j,t1]; {заменяем стоимость}
Pred[j,t1]:=Bliz; Typp[j,t1]:=bt; {запоминаем}
end; {предыдущие город и тип дороги}
При вычислении стоимости проезда через ближайшую вершину учитывается страховой сбор при переходе с дороги одного типа на дорогу другого типа с помощью функции C(t1,t2):
function C(t1,t2:byte):real;
begin
if t1=t2 then C:=1.0 else C:=1.1
end;
Вывод результатов осуществляется так:
G:=B; is:=0; {Текущий город — конечный город}
if d[B,0]
then t:=0 else t:=1; {лучший из двух возможных}
stt[1]:=t; {Текущий тип — выбранный лучший}
while (G0) do {Пока текущий город не равен 0}
begin
inc(is); {Инкрементируем количество городов}
stg[is]:=divd[G,t]; {сохраняем текущий город в путь}
stt[is+1]:=typp[G,t]; {и его тип}
NG:=divd[G,t]; {Переустанавливаем текущие город}
NT:=typp[G,T]; {и тип на предыдущие город}
G:=NG; t:=NT; {и тип}
end;
writeln(min(d[B,0],d[B,1]):0:2); {выводим минимальную стоимость}
for i:=is-1 downto 1 do writeln(stg[i],' ',stt[i]); {и путь}
writeln(B); {добавляем в путь последний город}
Далее приводится полный текст решения задачи.
{$R+,E+,N+}
program by98d1m2;
const
FREE = 0;
DONE = 1;
MAXR = 1e4;
var
p: array [1..80,1..80,0..1] of single;
D: array [1..80,0..1] of single;
divd: array [1..80,0..1] of 0..100;
typp,Labl: array [1..80,0..1] of 0..1;
stg: array [1..100] of 0..100;
stt: array [1..100] of 0..1;
M: 0..1000;
N,x,y,A,B,i,k,j,G,NG: 0..100;
t,t1,t2,bt,NT: 0..1;
is,Bliz: 0..100;
Mind: single;
Mint,MT: byte;
function C(t1,t2:byte):real;
begin
if t1=t2 then C:=1.0 else C:=1.1
end;
function min(x,y:single):single;
begin
if x
end;
begin
assign(input,'tour.in'); reset(input);
assign(output,'tour.out'); rewrite(output);
read(N);
read(M);
for x:=1 to N do
for y:=1 to N do
for t:=0 to 1 do p[x,y,t]:=MAXR;
for i:=1 to M do
begin
readln (x,y,t,p[x,y,t]); p[y,x,t]:=p[x,y,t];
end;
read(A,B);
for i:=1 to N do
for t:=0 to 1 do p[a,i,t]:=1.1*p[a,i,t];
for i:=1 to N do
begin D[i,0]:=P[a,i,0]; D[i,1] :=P[a,i,1]; end;
for i:=1 to N do
begin
Labl[i,0]:=FREE; Labl[i,1]:=FREE;
divd[i,0]:=A; divd[i,1]:=A;
end;
Labl[A,0]:=DONE; Labl[A,1]:=DONE; divd[A,0]:=0; Pred[A,1]:=0;
for i:=1 to 2*N-2 do
begin
MinD:=MaxR;
for J:=1 to N do
for t:=0 to 1 do
if (Labl[j,t]=FREE) and (minD>d[j,t])
then begin
Bliz:=j; bt:=t; MinD:=d[j,t]
end;
Labl[Bliz,bt]:=DONE;
for j:=1 to N do
for t1:=0 to 1 do
if (Labl[j,t1]=FREE) and
(d[j,t1]>d[Bliz,bt] + C(t1,bt)*P[Bliz,j,t1])
then begin
d[j,t1]:=d[Bliz,bt]+C(t1,bt)*P[Bliz,j,t1];
Pred[j,t1]:=Bliz; Typp[j,t1]:=bt;
end;
end;
G:=B; is:=0;
if d[B,0]
stt[1]:=t;
while (G0) do
begin
inc(is);
stg[is]:=divd[G,t]; stt[is+1]:=typp[G,t];
NG:=divd[G,t]; NT:=typp[G,T];
G:=NG; t:=NT;
end;
writeln (min(d[B,0],d[B,1]):0:2);
for i:=is-1 downto 1 do writeln(stg[i],' ',stt[i]);
writeln(B);
close(input); close(output);
end.
3. Поиск в глубину Ниже приведен пример неориентированного графа с шестью вершинами.
(1)--(3) (5)
I \ / I I
I / \ I I
(2)--(4) (6)
При компьютерной обработке граф может задаваться списком ребер (дуг) для каждой вершины. Например, для графа, приведенного на примере, этот список выглядит так
продолжение
--PAGE_BREAK--1: 2,3,4 (первая вершина соединена со второй, третьей и четвертой)
2: 1,3,4
3: 2,3,4
4: 1,2,3
5: 6
6: 5
Для хранения этой информации в памяти компьютера можно воспользоваться двумерным массивом G[1..N,1..M], где N — число вершин в графе, M — максимально возможное число ребер (дуг) у одной вершины графа. Для удобства обработки этой информации можно также иметь одномерный массив kG[1..N] — количества ребер (дуг) вершин графа.
Тогда для обработки списка связей текущей вершины U можно написать
for i:=1 to kG[U]
begin
V:=G[U,i];
end;
Тем самым, мы получаем обработку дуги, связывающей вершины U и V для всех вершин, непосредственно связанных с U.
Для обработки ВСЕХ связей всех вершин можно использовать поиск в глубину (DFS — Depth-First Search):
for U:=1 to N do Color[U]:=WHITE;
for U:=1 to N do
if color[U]=WHITE then DFS(U);
Procedure DFS(U:longint);
var
j: longint;
begin
color[U]:=GRAY;
for j:=1 to kG[U] do DFS(G[U,j]);
end;
Здесь
Color[U] = цвет вершины
WHITE (константа=1) — белый,
если мы еще не посещали эту вершину
GRAY (константа=2) — серый,
если мы посещали данную вершину
DFS(U) — рекурсивная процедура, которая вызывает себя
для всех вершин, потомков данной вершины.
То есть, для обеспечения поиска в глубину на заданном графе G[1..N,1..M] с количествами дуг из вершин G[1..N], вначале мы устанавливаем всем вершинам цвет WHITE, а затем для всех вершин, которые еще не посещались (Color[G[U,j]]=WHITE) вызываем рекурсивную процедуру DFS.
Таким способом формируются все возможные маршруты в графе.При этом нет ограничений на количество раз использования дуг и заходов в вершины.
Если же по условиям задачи потребуется посещать каждую вершину не более одного раза, чтобы формировать маршруты из несовпадающих вершин, то это может быть обеспечено в процедуре DFS условным вызовом:
Procedure DFS(U:longint);
var
j: longint;
begin
color[U]:=GRAY;
for j:=1 to kG[U] do
if color[G[U,j]]=WHITE then DFS(G[U,j]);
end;
Если по условиям задачи требуется каждую дугу использовать не более одного раза, то можно ввести расцветку дуг:
Color[1..N,1..M] — со значениями FREE или DONE
где, как и ранее
N — число вершин в графе,
M — максимально возможное число ребер (дуг) у одной вершины графа.
А процедура DFS формирования маршрутов так, что бы каждая дуга использовалась в маршруте не более одного раза, будет выглядеть следующим образом:
procedure DFS(v:byte);
var j: byte;
begin
for j:=1 to kG[v] do
if (color[v,j]=FREE)
then
begin
color[v,j]:=DONE;
DFS(G[v,j]);
color[v,j]:=FREE;
end;
end;
Здесь вводятся пометки на дуги Color[v,j] = FREE, если дуга еще не обработана, и DONE, если она включена в текущий путь.
Если в задаче требуется вывести найденный путь, то для его хранения заводится специальный массив SLED [1..Q], где Q — максимальное количество ребер в пути и вершины текущего пути заносятся в этот массив и удаляются из него в процессе обхода графа:
procedure DFS(v:byte);
var j: byte;
begin
for j:=1 to kG[v] do
begin
inc(ks); sled[ks]:=G[v,j];
DFS(G[v,j]);
dec(ks);
…
end;
end;
Приведенная теоретическая информация иллюстрируется далее примерами решения конкретных задач.
3.1 Задача «Дороги» Республиканская олимпиада по информатике 1997г
Дана система односторонних дорог, определяемая набором пар городов. Каждая такая пара (i,j) указывает, что из города i можно проехать в город j, но это не значит, что можно проехать в обратном направлении.
Необходимо определить, можно ли проехать из заданного города А в заданный город В таким образом, чтобы посетить город С и не проезжать ни по какой дороге более одного раза.
Входные данные задаются в файле с именем PATH.IN следующим образом. В первой строке находится натуральное N(N
Ответом является последовательность городов, начинающаяся городом А и заканчивающаяся городом В, удовлетворяющая условиям задачи, который должен быть записан в файл PATH.OUT в виде последовательности номеров городов по одному номеру в строке. Первая строка файла должна содержать количество городов в последовательности. При отсутствии пути записать в первую строку файла число -1.
Пример Ответ
3 3
2 1
1 2 2
2 3 3
1 3 2
Кратко идея решения может быть изложена следующим образом:
Поиск в глубину.
Если встречаем вершину B, устанавливаем соответствующий флаг.
Если встречаем вершину C и флаг B установлен — выводим результат и завершаем работу.
После завершения поиска (требуемый маршрут не найден) выводим -1.
Изложим решение более подробно.
Ввод исходных данных осуществляется следующим образом:
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);
Здесь, как и прежде,
kG[i] — количество дуг из вершины i
G[i,j] — (для j от 1 до kG[j]) — вершины, с которыми вершина i связана соответствующей дугой/
Кроме того, введен цвет дуги
FREE — свободна (DONE — занята, FREE/DONE — константы)
Главная программа фактически включает только следующие операторы:
LabC:=0; {Установить метку — вершину C еще не посещали}
DFS(A); {Поиск в глубину от вершины A}
writeln(-1); {Вывод признака отсутствия требуемого пути}
Рекурсивная процедура поиска в глубину от вершины V выглядит следующим образом:
procedure DFS(v:byte);
var j: byte;
begin
for j:=1 to kG[v] do
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;
То есть для всех еще необработанных (color[v,j]=FREE) дуг от текущей вершины выясняем — если она ведет в конечный пункт, а город C уже проходили — вызов процедуры вывода результата и останов.
Если текущая дуга ведет в город С, устанавливаем соответствующую метку (LabC=1).
Помечаем дугу как обработанную, заносим ее в массив SLED, который содержит текущий обрабатываемый путь, KS — количество элементов в нем.
Вызываем процедуру DFS от вершины (G[v,j]), в которую ведет текущая дуга.
Перед выходом из процедуры DFS восстанавливаем состояние, «исходное» перед ее вызовом: снимаем отметку обработки с дуги (color[v,j]:=FREE), удаляем ее из массива SLED (dec(ks), оператор sled[ks]:=0; делать необязательно, но он предоставляет удобства отладки — что бы в масcиве SLED ненулевыми были только реально входящие в путь элементы).
И, наконец, процедура вывода результата:
procedure OutRes;
begin
writeln(ks+2);
writeln(A); for i:=1 to ks do writeln(sled[i]); writeln(B);
end;
Поскольку по алгоритму построения начальный (A) и конечный (B) города не заносились в массив SLED, то они выводятся отдельно, а количество городов в пути (KS) перед выводом увеличивается на 2.
Полный текст программы приводится ниже.
program by97d2s3;
const
FREE=1;
DONE=2;
var
G,color: array[1..50,1..100] of byte;
D: array[1..50] of longint;
kG,sled: array[1..50] of byte;
path: array[1..100] of byte;
MinD,is: longint;
i,j,x,y,A,B,C,N,M,ks,LabC: byte;
Yes: boolean;
procedure OutRes;
begin
writeln(ks+2);
writeln(A); for i:=1 to ks do writeln(sled[i]); writeln(B);
end;
procedure DFS(v:byte);
var j: byte;
begin
for j:=1 to kG[v] do
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);
nd.
3.2 Задача «Перекрестки» (Автор — Котов В.М.)
Республиканская олимпиада по информатике 1998г
Даны декартовы координаты N перекрестков города, которые пронумерованы от 1 до N. На каждом перекрестке имеется светофор. Некоторые из перекрестков соединены дорогами с двухсторонним (правосторонним) движением, которые пересекаются только на перекрестках. Для каждой дороги известно время, которое требуется для проезда по ней от одного перекрестка до другого.
Необходимо проехать от перекрестка с номером А до перекрестка с номером В за минимальное время.
Время проезда зависит от набора проезжаемых дорог и от времени ожидания на перекрестках. Так, если вы подъехали от перекрестка X к перекрестку C по дороге Х->C и хотите ехать дальше по дороге C->У, то время ожидания на перекрестке C эависит от того, поворачиваете ли вы налево или нет. Если вы поворачиваете налево, то время ожидания равно D*К, где D равно количеству дорог, пересекающихся на перекрестке C, а К — некоторая константа. Если вы не поворачиваете налево, то время ожидания равно нулю.
Написать программу, которая определяет самый быстрый маршрут.
Спецификация входных данных.
Входные данные находятся в текстовом файле с именем PER.IN и имеют следующую структуру:
— в первой строке находится число N (натуральное,
— во второй строке — количество дорог M (натуральное,
— в третьей строке — константа K (натуральное число,
— в каждой из N следующих стpок находится паpа чисел х и у, разделенных пробелом, где x, y — кооpдинаты перекрестка (целые числа, не пpевышающие по модулю 1000);
— в каждой из M следующих строк находится 3 числа p, r, t, разделенные пробелом, где p и r — номера перекрестков, которые соединяет дорога, а t (натуральное,
— в последней строке находятся номера начального А и конечного В перекрестков.
Спецификация выходных данных.
Выходные данные должны быть записаны в текстовый файл с именем 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) обеспечивает выполнение cледующей работы:
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
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)
(((x2
(((y2=y1) and (x1>x2) and (y3
(((y2=y1) and (x1y1))) or
(((x2=x1) and (y1>y2) and (x3>x1))) or
(((x2=x1) and (y1
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
then begin
OptT:=T;
OptKv:=kv; OptSled:=Sled;
end;
Sled[kv]:=0; dec(kv);
Таким образом, оптимальное время хранится в переменной OptT а оптимальный путь храниться в массиве OptSled с количеством элементов OptKv. И потому, вывод результатов выглядит так:
writeln(OptT);
for i:=1 to OptKv do writeln(OptSled[i]);
Полный текст программы приводится ниже
program by98d2s2;
Const
FREE = 1;
DONE = 2;
Type
продолжение
--PAGE_BREAK--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,divd: 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)
(((x2
(((y2=y1) and (x1>x2) and (y3
(((y2=y1) and (x1y1))) or
(((x2=x1) and (y1>y2) and (x3>x1))) or
(((x2=x1) and (y1
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
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
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.
3.3 Задача «Скрудж Мак-Дак» (Автор — Котов В.М.) Республиканская олимпиада по информатике 1995г
Скрудж Мак-Дак решил сделать прибор для управления самолетом. Как известно, положение штурвала зависит от состояния входных датчиков, но эта функция довольно сложна.
Его механик Винт Р. сделал устройство, вычисляющее эту функцию в несколько этапов с использование промежуточной памяти и вспомогательных функций. Для вычисления каждой из функций требуется, чтобы в ячейках памяти уже находились вычисленные параметры (которые являются значениями вычисленных функций), необходимые для ее вычисления. Вычисление функции без параметров может производится в любое время.
После вычисления функции ячейки могут быть использованы повторно (хотя бы для записи результата вычисленной функции). Структура вызова функций такова, что каждая функция вычисляется не более одного раза и любой параметр используется не более одного раза. Любой параметр есть имя функции. Так как Скрудж не хочет тратить лишних денег на микросхемы, он поставил задачу минимизировать память прибора. По заданной структуре вызовов функций необходимо определить минимальный возможный размер памяти прибора и указать последовательность вычисления функций.
Входной файл INPUT.TXT
Формат ввода:
1 строка>
2 строка>
3 строка> []
…
N+2 строка> []
Выходной файл OUTPUT.TXT
Формат вывода:
Размер памяти (в ячейках)
имя 1-й вычисляемой функции
имя 2-й вычисляемой функции
…
имя функции, которую необходимо вычислить
Примечание: имя функции есть натуральное число от 1 до N.
Пример.
Ввод Вывод
5 Размер памяти: 2 ячейки
1 Порядок:
1 2 2 3 Функция 4
2 0 Функция 5
3 2 4 5 Функция 3
4 0 Функция 2
5 0 Функция 1
В кратком изложении в данной задаче требуется сделать следующее:
— найти S — максимальную степень среди тех вершин, что подлежат обходу (поиск в глубину DFS1)
— необходимая память вычисляется по формуле
MaxS = S + k -1
где S — найдено на предыдущем шаге (DFS1),
а k — максимальное количество вершин одного уровня вложенности с такой же степенью S.
Для вычисления k совершается обход повторным поиском в глубину DFS2
— третьим поиском в глубину DFS3 находим и помещаем в очередь V все вершины, степень которых равна S.
— последним, четвертым поиском в глубину обходим данное дерево в порядке вершин в очереди V. То есть, в первую очередь вычисляем те функции, для которых требуется максимальная память.
Рассмотрим реализацию алгоритма более подробно.
Ввод исходных данных осуществляется следующим образом:
Read (N,FC);
for i:=1 to N do
begin
read(f,kG[f]);
for j:=1 to kG[f] do read(G[f,j]);
end;
Здесь
N — исходное количество вершин,
FC — номер функции, которую нужно вычислить
kG[i] — количество параметров для вычисления функции i
G[i,j] — j-тый параметр, требуемый для вычисления функции i
Тело главной программы выглядит так:
for i:=1 to N do color[i]:=WHITE; {пометить свободными все вершины}
DFS1(FC); {находим S — максимальную степень вершин используемых для вычисления функции FC}
MaxS:=S;
DFS2(FC); {Вычисляем
K — количество вершин со степенью S в текущем слое и
MaxS — максимальная из значений по слоям величина S+K-1}
kv:=0;
DFS3(FC); {Поместить в массив V все вершины, степень которых равна S, количество таких вершин — в переменной kv}
kr:=0;
for i:=1 to kv do DFS4(v[i]); {Обход графа поиском в глубину начиная с вершин с максимальной степенью из массива V.
Найденные вершины заносить в массив r}
writeln(MaxS); {вывод количества ячеек памяти}
for i:=1 to kr do writeln(r[i]); {вывод порядка вычисления функций}
Полное решение задачи приводится ниже
program by95d2t1;
const
WHITE = 1;
GRAY = 2;
BLACK = 3;
var
G: array [1..100,1..100] of longint;
kG,v,color,r: array [1..100] of longint;
N,FC,i,j,s,f,kv,MaxS,kr: longint;
procedure DFS1(u:longint);
var
i,k: longint;
begin
if s
for i:=1 to kG[u] do DFS1(G[u,i]);
end;
procedure DFS2(u:longint);
var
i,k: longint;
begin
k:=0;
for i:=1 to kG[u] do
if kG[G[i,j]]=s then inc(k);
if MaxS
for i:=1 to kG[u] do DFS2(G[u,i]);
end;
procedure DFS3(u:longint);
var
i,k: longint;
begin
if kG[u]=s
then
begin
for i:=1 to kG[u] do DFS3(G[u,i]);
nc(kv); v[kv]:=u;
end;
end;
procedure DFS4(u:longint);
var
i: longint;
begin
color[u]:=GRAY;
if kG[u]0
then
for i:=1 to kG[u] do
if color[G[u,i]]GRAY
then DFS4(G[u,i]);
inc(kr); r[kr]:=u;
end;
begin
assign(input,'input.txt'); reset(input);
assign(output,'output.txt'); rewrite(output);
read(N,FC);
for i:=1 to N do
begin
read(f,kG[f]);
for j:=1 to kG[f] do read(G[f,j]);
end;
for i:=1 to N do color[i]:=WHITE;
DFS1(FC);
MaxS:=s; DFS2(FC);
kv:=0; DFS3(FC);
kr:=0; for i:=1 to kv do DFS4(v[i]);
writeln(MaxS);
for i:=1 to kr do writeln(r[i]);
close(input); close(output);
end.
4. Сильносвязные компоненты и доминантные множества Подграф графа называется его сильносвязной компонентой, если каждая из вершин подграфа достижима от любой из верши подграфа.
Доминантное множество — это минимальное множество вершин графа, из которого достижимы все вершины графа.
Алгоритмы построения сильносвязных компонент и доминантных множеств графа рассмотрим на примерах.
4.1 Задача «Карточки» Республиканская олимпиада по информатике 1994г
1. Есть N карточек. На каждой из них черными чернилами написан ее уникальный номер — число от 1 до N. Также на каждой карточке красными чернилами написано еще одно целое число, лежащее в промежутке от 1 до N (некоторыми одинаковыми «красными» числами могут помечаться несколько карточек).
Например, N=5, 5 карточек помечены следующим образом:
—
«черное» число ¦ 1¦ 2¦ 3¦ 4¦ 5¦
—
«красное» число ¦ 3¦ 3¦ 2¦ 4¦ 2¦
—
Необходимо выбрать из данных N карточек максимальное число карточек таким образом, чтобы множества «красных» и «черных» чисел на них совпадали.
Для примера выше это будут карточки с «черными» номерами 2, 3, 4 (множество красных номеров, как и требуется в задаче, то же — {2,3,4}).
ВВОД: N, N
«красное»_число_1
…
«красное»_число_N
ВЫВОД:
S
a1, ..., aS
Пример ввода Пример вывода
6 6
1 2 1
2 3 2
3 4 3
4 5 4
5 1 5
6 6 6
Фактически в задаче требуется найти все сильно связные компоненты представляемого карточками ориентированного графа и добавить к ним карточки, на которых и красным и черным цветом написаны одни и те же числа.
Опишем решение задачи более подробно, опираясь на исходный текст соответствующей программы.
Тело главной части программы будет выглядеть так:
readln(N); {Читаем количество карточек}
M:=0; {Количество карточек в результате}
for i:=1 to N do {Для всех карточек}
begin
readln(u,v); {Читаем карточку}
inc(kG[u]); G[u,kG[u]]:=v; {Пополняем по ней граф}
if u=v {Если красное число равно черному}
then
begin inc(M); T[M]:=u;end; {заносим карточку в результат}
end;
BuildDominators; {Строим множество доминаторов}
Reverse; {Обращаем граф}
BuildDominators2; {Строим множество доминаторов обращенного графа, попутно получая все сильносвязные компоненты графа}
Рассмотрим процедуру BuildDominators:
Procedure BuildDominators;
begin
Time:=0; {Время обработки вершин = 0}
for i:=1 to N do {Для каждой вершины i помечаем}
begin
Color[i] := WHITE; {Вершина свободна}
Dom[i] := WHITE; {Доминаторов нет}
CurC[i] := WHITE; {Свободна на текущем шаге}
F[i] := 0; {Время завершения обработки — 0}
end;
for v:=1 to N do {Для всех вершин}
if color[v]=WHITE {Если вершина v свободна}
then
begin
DFS(v); {Поиск в глубину от вершины v}
AddDominator(v); {Добавить найденного доминатора}
end;
end;
Таким образом в ходе обработки вершин графа на этом этапе у нас есть 3 множества
Dom — найденные на текущий момент доминаторы графа
Color — все обработанные вершины
CurC — вершины, обработанные во время поиска в глубину от текущей базовой вершины V
Рекурсивная процедура поиска в глубину выглядит для данной задачи таким образом:
Procedure DFS(i:byte);
var
j: byte;
begin
color[i]:=GRAY; {Вершина i обработана вообще}
curC[i]:=GRAY; {Вершина i обработана на текущем шаге}
inc(Time); {Увеличить время обработки вершин}
for j:=1 to kG[i] do {Пока у вершины есть наследники}
if curC[G[i,j]]=WHITE {Если наследник не обрабатывался на текущем шагу}
then DFS(G[i,j]); {Запустить поиск в глубину от наследника}
inc(Time); {Увеличить время обработки вершин}
if F[i]=0 {Если вершине i не устанавливалось время}
then F[i]:=Time; {завершения обработки — то установить}
end;
Процедура AddDominator(v), также вызываемая из процедуры BuildDominators, добавляет в список доминаторов вершину v следующим образом: все вершины, достигнутые из текущей (Curc[i]WHITE) вычеркиваем из доминаторов; текущую добавляем в список доминаторов (dom[Domi]:=GRAY;).
Procedure AddDominator (Domi:longint);
begin
for i:=1 to N do {Для всех вершин}
if (CurC[i]WHITE) {Если она достигнута от текущей}
then dom[i]:=WHITE; {Вычеркиваем ее из доминаторов}
dom[Domi]:=GRAY; {Вносим текущую в список доминаторов}
for i:=1 to N do {Для всех вершин устанавливем отметку}
curC[i]:=WHITE; {недостигнута от текущей}
end;
Следующий шаг за построением доминаторов исходного графа — транспонирование графа (другими словами смена стрелок на дугах на противоположные). Это делается с помощью процедуры Reverse. Процедура Reverse по исходному графу G[1..N,1..M], kg[1..N] строит граф B[1..N,1..M], kB[1..N]:
Procedure Reverse;
begin
for i:=1 to N do KB[i]:=0; {Обнуляем количества дуг из вершины i}
for i:=1 to N do
for j:=1 to kG[i] do
begin
inc(kB[G[i,j]]); {Инкрементируем количество дуг из вершины i}
b[G[i,j],kB[G[i,j]]]:=i; {Добавляем в граф обратную дугу}
end;
end;
Процедура BuildDominator2 строит множество доминаторов на транспонированном графе, параллельно формируя сильно связные компоненты (ССК) исходного графа:
Procedure BuildDominators2;
begin
Time:=0;
for i:=1 to N do {Для всех вершин}
begin
Color[i]:=WHITE; {Свободна вообще}
CurC[i] :=WHITE; {Свободна в текущем цикле}
Kart[i]:=WHITE; {Не входит в ССК}
end;
SortF; {Сортируем в порядке убывания времена завершения обработки вершин при построении множества доминаторов исходного графа — результат Q[1..N]}
for v:=1 to N do {В порядке убывания времен обработки}
if color[Q[v]]=WHITE {Если вершина свободна}
then
begin
DFS2(Q[v]); {Построить доминатора}
AddDominator2(Q[v]); {Добавить доминатора}
end;
for i:=1 to N do {Для всех вершин}
if (Kart[i]WHITE) {Если входит в ССК}
then begin
inc(M); {вносим в результат}
T[M]:=i;
end;
SortT; {Сортируем результирующее множество}
writeln(M); for i:=1 to M do writeln (T[i]); {выводим его}
end;
Процедура DFS2 поиска глубину по транспонированному графу выглядит следующим образом:
Procedure DFS2(i:byte);
Var j: byte;
begin
color[i]:=GRAY; curc[i]:=GRAY;
for j:=1 to kB[i] do
if color[B[i,j]]=WHITE then DFS2(B[i,j]);
end;
Процедура AddDominator2 обеспечивающая корректное построение доминаторов транспонированного графа и сильносвязных компонент исходного (и транспонированного) графов такова:
Procedure AddDominator2 (Domi:longint);
var
MinT, MinK, KS: longint;
FlDom: boolean;
begin
KS:=0; {Количество вершин в текущей ССК}
for i:=1 to N do {Для всех вершин}
if Curc[i]WHITE {Если вершина достигнута}
then inc(KS); {инкрементировать к-во вершин в текущей ССК}
if ks>1 {Если в текущей ССК вершин}
then {больше чем одна}
for i:=1 to N do {то внести их всех в KART}
if CurC[i]WHITE then Kart[i]:=GRAY;
for i:=1 to N do curC[i]:=WHITE; {Сделать все вершины свободными для нового шага}
end;
Полный текст программы, решающей поставленную задачу приводится ниже.
program by94d1t1;
Const
WHITE = 1;
GRAY = 2;
var
G,B: array [1..100,1..100] of byte;
Color,kG,kB,Dom,CurC,Kart: array [1..100] of byte;
D,F,T,Q: array [1..100] of longint;
N,i,j,Time,v,u,M,GRA_Y: longint;
Function max(a,b:longint):longint;
begin
if (a>b) then max:=a else max:=b
end;
Procedure Reverse;
begin
for i:=1 to N do KB[i]:=0;
for i:=1 to N do
for j:=1 to kG[i] do
begin
inc(kB[G[i,j]]);
b[G[i,j],kB[G[i,j]]]:=i;
end;
end;
Procedure AddDominator (Domi:longint);
begin
for i:=1 to N do
if CurC[i]WHITE then dom[i]:=WHITE;
dom[Domi]:=GRAY;
for i:=1 to N do curC[i]:=WHITE;
end;
Procedure DFS(i:byte);
Var j: byte;
begin
color[i]:=GRAY; curC[i]:=GRAY; inc(Time);
for j:=1 to kG[i] do
if curC[G[i,j]]=WHITE then DFS(G[i,j]);
inc(Time);
if F[i]=0 then F[i]:=Time;
end;
Procedure BuildDominators;
begin
Time:=0;
for i:=1 to N do
begin
Color[i]:=WHITE; Dom[i]:=WHITE;
CurC[i]:=WHITE; F[i]:=0;
end;
for v:=1 to N do
if color[v]=WHITE
then begin DFS(v); AddDominator(v); end;
end;
Procedure SortF;
var
i,j,MaxD,k,Temp :longint;
begin
for i:=1 to N do Q[i]:=i;
for i:=1 to N-1 do
begin
MaxD:=F[i]; K:=i;
for j:=i+1 to N do
if F[j]>MaxD
then begin MaxD:=F[j]; k:=j; end;
F[k]:=F[i]; F[i]:=MaxD; Temp:=Q[k];
Q[k]:=Q[i]; Q[i]:=Temp;
end
end;
продолжение
--PAGE_BREAK--