Вхідний файл: input2.txt Вихідний файл: output2.txt
Формат вводу:
N
M
R11 T11 R12 T12
RM1 TM1 RM2 TM2
де N (2 <= N <= 100) - кількість кімнат
M (M <= 100) - кількість пристроїв
Ri1 і Ri2 - номери кімнат, у яких розташовуються модулі пристрою i Ti1, Ti2 (Ti1, Ti2 <= 1000) - періоди часу, через які спрацьовують ці модулі Всі числа - натуральні.
Приклад
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 (a <> b) do if a> b then a: = ab else b: = ba;
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) {і відстань від неї до першої}
{Вершини менше 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 tg <> 0 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 (a <> b) do
if a> b then a: = ab else b: = ba;
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] <MinD)
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 tg <> 0 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 <N <= 100). Деякі з них з'єднані двосторонніми дорогами, які перетинаються лише в містах. Є два типи доріг - шосейні і залізні. Для кожної дороги відома базова вартість проїзду по ній.
Необхідно проїхати з міста А в місто В, сплативши мінімальну суму за проїзд. Вартість проїзду залежить від набору проїжджаємо доріг і від способу проїзду. Так, якщо ви під'їхали до міста З по шосейній (залізної) дорозі X-> C і хочете їхати далі по дорозі C-> Y того ж типу, то ви повинні сплатити тільки базову вартість проїзду по дорозі C-> Y. Якщо тип дороги C-> Y різниться від типу дороги Х-> C, то ви повинні сплатити базову вартість проїзду по дорозі C-> Y плюс 10% від базової вартості проїзду по цій дорозі (страховий внесок). При виїзді з міста А страховий внесок сплачується завжди. Написати програму, яка знаходить найдешевший маршрут проїзду у вигляді послідовності міст і обчислює вартість проїзду за цим маршрутом.
Специфікація вхідних даних
Вхідні дані знаходяться у текстовому файлі з ім'ям TOUR.IN і мають наступний формат:
- У першому рядку знаходяться число N
- У другому рядку - число M (кількість доріг, натуральне M <= 1000);
- В кожній з наступних M рядків знаходяться 4 числа x, y, t, p, розділені пробілом, де x і y - номери міст, які з'єднує дорога, t - тип дороги (0 - шосейна, 1 - залізна), p - базова вартість проїзду по ній (p - дійсне, 0 <p <= 1000).
- В останньому рядку задається номери початкового і кінцевого міст 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
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] <d [B, 1] {Тип в'їзду -}
then t: = 0 else t: = 1; {кращий з двох можливих}
stt [1]: = t; {Поточний тип - обраний кращий}
while (G <> 0) 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 <= y then min: = x else min: = y
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] <d [B, 1] then t: = 0 else t: = 1;
stt [1]: = t;
while (G <> 0) 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 / II
I / \ II
(2) - (4) (6)
При комп'ютерній обробці граф може задаватися списком ребер (дуг) для кожної вершини. Наприклад, для графа, наведеного на прикладі, цей список виглядає так
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 <= 50) - кількість міст (міста нумеруються від 1 до N). У другому рядку знаходиться натуральне M (M <= 100) - кількість доріг. Далі в кожному рядку знаходиться пара номерів міст, які пов'язує дорога. В останній (M +3)-му рядку знаходяться номери міст А, В і С.
Відповіддю є послідовність міст, що починається містом А і закінчується містом В, що задовольняє умовам задачі, який повинен бути записаний у файл PATH.OUT у вигляді послідовності номерів міст по одному номеру в рядку. Перший рядок файлу повинна містити кількість міст в послідовності. При відсутності шляху записати в перший рядок файлу число -1.
Приклад Відповідь
3 березня
2 Січень
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 (натуральне, <= 1000);
- У другому рядку - кількість доріг M (натуральне, <= 1000);
- В третьому рядку - константа K (натуральне число, <= 1000);
- В кожній з N наступних стpок знаходиться паpа чисел х і у, розділених пробілом, де x, y - коо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);
for i: = 1 to OptKv do writeln (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, 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) <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.

3.3 Завдання "Скрудж Мак-Дак" (Автор - Котов В.М.)

Республіканська олімпіада з інформатики 1995
Скрудж Мак-Дак вирішив зробити прилад для керування літаком. Як відомо, положення штурвала залежить від стану вхідних датчиків, але ця функція досить складна.
Його механік Гвинт Р. зробив пристрій, обчислює цю функцію в кілька етапів з використання проміжної пам'яті і допоміжних функцій. Для обчислення кожної з функцій потрібно, щоб у комірках пам'яті вже перебували обчислені параметри (які є значеннями обчислених функцій), необхідні для її обчислення. Обчислення функції без параметрів може проводиться в будь-який час.
Після обчислення функції осередки можуть бути використані повторно (хоча б для запису результату обчисленої функції). Структура виклику функцій така, що кожна функція обчислюється не більше одного разу і будь-який параметр використовується не більше одного разу. Будь-який параметр є ім'я функції. Так як Скрудж не хоче витрачати зайвих грошей на мікросхеми, він поставив завдання мінімізувати пам'ять приладу. За заданою структурі викликів функцій необхідно визначити мінімальний можливий розмір пам'яті приладу і вказати послідовність обчислення функцій.
Вхідний файл INPUT.TXT
Формат вводу:
1 рядок> <загальна кількість функцій N>
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 <kG [u] then s: = kG [u];
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 <s + k-1 then MaxS: = s + k-1;
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}).

ENTER: <N=> N, N <= 50
<"Чорний" номер 1, "червоний" -> "червоне" _чісло_1
......
<"Чорний" номер N, "червоний" -> "червоне" _чісло_N
ВИСНОВОК:
<В обраному безлічі елементів кількість елементів> S
<"Чорні" номери обраних карток> a1, ..., aS
Приклад введення Приклад виводу
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;