Республика, школьники, 1995г.

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

Тактика хаккеров.

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

Например, захватить все ЭВМ. Но хаккеры всегда выбирают такой вариант, при котором суммарное количество терминалов у захваченных ЭВМ минимально.

Примечание.

В сети Винни-Пуха и Пятачка ни у каких 2-х ЭВМ количество терминалов не совпадает.

Техническое задание.

Вам необходимо написать программу, входными данными которой было бы описание сети, а выходными - список номеров ЭВМ, которые могут быть выбраны хаккерами для захвата сети согласно их тактике. Ввод осуществляется из файла с именем INPUT.TXT. Возможен ввод с клавиатуры.

Формат ввода.

Количество ЭВМ в сети : N

ЭВМ #1 имеет терминалов : T[1]

ЭВМ #2 имеет терминалов : T[2]

...

ЭВМ #N имеет терминалов : T[N]

Права на запрос :

A[1] B[1]

A[2] B[2]

...

A[K] B[K]

0 0

A[i] и В[i] - номера ЭВМ, последняя строка '0 0' обозначает конец списка прав на запрос, каждая пара A[i] B[i] обозначает, что ЭВМ с номеров A[i] имеет право запрашивать информацию у ЭВМ с номером B[i] (A[i] не равно B[i]).

При вводе числа N и T[i] - натуральные, T[i] <=1000, N<=50, K<=2450.

Входные данные соответствуют приведенным условиям.

Формат вывода.

Номера захватываемых ЭВМ : С[1] C[2] ... С[M].

Количество захватываемых ЭВМ : <M>

Input.txt

5

100

2

1

3

10

1 3

3 2

4 3

4 5

5 4

0 0

Output.txt

1 4

2

Поиском в глубину находим множество доминаторов сети. (истоки графа). Однако для оптимального выбора машин по количеству терминалов необходимо выбрать лучшую машину (с наименьшим количеством терминалов) в каждой сильно связной компоненте.

Для этого инвертируем граф (меняем направление всех дуг графа на противоположное) и поиском в глубину по инвертированному графу находим все его сильно связные компоненты (последовательные деревья, которые получаются поиском в глубину.). Нас интересуют только сильно связные компоненты с количеством вершин больше 1. В этом случае находим из них вершину с минимальным количеством терминалов и заменяем соответствующий доминатор (если от этой ССК ранее в доминаторы попала другая вершина).

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

5. Поиск в ширину

5.1 Задача "Уличная гонка"

IOI'95 - Международная олимпиада по информатике (Голландия)

1 4 7

/ \ / \ / \

/ \ / \ / \

/ \ / \ / \

0 3 6 9

\ / \ / \ /

\ / \ / \ /

\ / \ / \ /

2 5 <---8

Вы видите точки, помеченные числами от 0 до N (где N=9), а также стрелки, соединяющие их. Точка 0 является стартовой; точка N - финишной. Стрелками представлены улицы с односторонним движением. Участники гонки передвигаются от точки к точке по улицам только в направлении стрелок. В каждой точке участник гонки может выбрать любую из исходящих стрелок.

Назовем план улиц хорошим, если он обладает следующими свойствами:

1. Каждая точка плана может быть достигнута со старта.

2. Финиш может быть достигнут из любой точки плана.

3. У финиша нет исходящих стрелок.

Для достижения финиша участник не обязан пройти через все точки. Однако некоторые точки невозможно обойти. Назовем их неизбежными. В примере такими точками являются точки 0, 3, 6, 9. Для заданного хорошего плана Ваша программа должна определить множество неизбежных точек (за исключением старта и финиша), которые должны посетить все участники (подзадача А).

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

Точка S является точкой разбиения для хорошего плана С, если S отличается от старта и финиша С, и план разбивается ею на два хороших плана без общих стрелок и с единственной общей точкой S. В примере точкой разбиения является точка 3.

ВХОДНЫЕ ДАННЫЕ

В файле INPUT.TXT описан хороший план, содержащий не более 50 точек и не более 100 стрелок. В файле имеется N+1 строка. Первые N строк содержат конечные точки стрелок, исходящих соответственно из точек от 0 до N-1. Каждая из этих строк заканчивается числом -2. В последней строке содержится число -1.

ВЫХОДНЫЕ ДАННЫЕ

Ваша программа должна записать две строки в файл OUTPUT.TXT. Первая строка должна содержать количество неизбежных точек в заданном плане, после чего в той же строке должны следовать номера этих точек в любом порядке (подзадача А). Вторая строка должна содержать количество точек в заданном плане, за которым в той же строке должны следовать номера этих точек в любом порядке(подзадача В).

ПРИМЕР ВВОДА И ВЫВОДА

INPUT.TXT OUTPUT.TXT

1 2 -2 2 3 6

3 -2 1 3

3 -2

5 4 -2

6 4 -2

6 -2

7 8 -2

9 -2

5 9 -2

-1

Для решения подзадачи A нужно найти все неизбежные точки. Это делается поиском в ширину - если после взятия вершины из очереди очередь становится пустой - то эта вершина - НЕИЗБЕЖНАЯ.

Для решения подзадачи B нужно проверить каждую НЕИЗБЕЖНУЮ точку, является ли она точкой разбиения. Для этого удаляем эту точку из графа и поиском в ширину строим 2 множества - ДОСТИЖИМЫЕ точки от начала, и недостижимые точки от начала.

Если существует хоть одно ребро из недостижимой точки в достижимую - то текущая НЕИЗБЕЖНАЯ точка не является возможной точкой разбиения (по определению точки разбиения).

Рассмотрим алгоритм решения задачи более подробно, основываясь на исходном тексте программы, решающей поставленную задачу:

Тело главной программы выглядит следующим образом:

InputData; {Ввод исходных данных}

BFS; {Поиск в ширину - находим "неизбежные" точки}

OutSubA; {Вывод ответа для подзадачи A}

for k:=1 to SubA do {Для каждой неизбежной точки}

begin

DelArcs(Duty[k]); {Удаляем неизбежную точку}

BFS; {Поиск в ширину -}

{Строим множества достижимых Color[i]=1}

{и недостижимых Color[i]=0 вершин}

RetArcs(Duty[k]); {Возвращаем неизбежную точку в граф}

for i:=0 to N-1 do {Для всех веришин}

begin

j:=1; {j - номер дуги, исходящей из вершины}

while (a[i,j]>=0) do {пока дуга существует}

begin

if (color[i]=WHITE) and {Если исходная вершина достижима}

(color[a[i,j]]<>WHITE) {а "конец дуги" - не достижима}

then begin

Duty[k]:=0; {Это - НЕ точка разбиения}

break {Перейти к проверке следующей}

end; {неизбежной точки}

inc(j); {Взять следующую дугу}

end;

end;

end;

OutSubB; {Вывод ответа для подзадачи B}

Процедура ввода исходных данных:

Procedure Inputdata;

begin

i:=0; j:=1; read(a[0,1]); {начинаем ввод с вершины 0}

while (a[i,j]<>-1) do {Пока не закончена обработка вершин}

begin

while(a[i,j]<>-2) do {Пока не закончена обработка дуг}

begin

inc(j); {Увеличить номер дуги}

read(a[i,j]) {Прочитать дугу}

end;

if j >2 then Sort; {Если дуг больше чем одна, то}

{отсортировать их по возрастанию}

{номера конечной вершины}

readln; inc(i); {Перейти к считыванию следующей строки}

j:=1; read(a[i,j]); {Прочитать первый элемент строки}

end; {Вернуться к началу цикла ПОКА}

N:=i; {Занести в N номер последней вершины}

end;

Поиск в ширину осуществляется с помощью процедуры BFS (Breadth-First Search).

procedure BFS;

var i,j : longint;

begin

for i:=0 to N do color[i]:=WHITE; {Все вершины свободны}

color[0]:=GRAY; {Начальная вершина - обработана}

SubA:=0; {Количество неизбежных вершин = 0}

BegQ:=1; {Начало очереди}

EndQ:=0; {Очередь пуста}

Put(0); {Поместить в очередь начальную вершину}

while (BegQ<=EndQ) do {Пока очередь не пуста}

begin

Get(i); {Взять вершину i из очереди}

if BegQ>EndQ {Если очередь осталась пустой}

then

begin

inc(SubA); {инкрементировать количество}

{неизбежных вершин}

Color[i]:=ColSubA {Пометить неизбежную вершину}

end;

j:=1; {номер дуги из вершины i}

while (a[i,j]>=0) do {пока дуги не кончились}

begin

if color[a[i,j]]=WHITE {если вершина a[i,j] свободна}

then

begin

Put(a[i,j]); {поставить ее в очередь}

color[a[i,j]]:=GRAY; {пометить вершину a[i,j]}

end; {как использованную}

inc(j); {взять следующую дугу}

end;

end;

end;

Вывод ответа для подзадачи A и накопление неизбежных точек в массив Duty осуществляется так:

procedure OutSubA;

begin

SubA:=subA-2; {Начальная и конечная точки не}

write(subA); {считаются неизбежными точками}

j:=0; {J - количество неизбежных точек}

for i:=1 to N-1 do {Для всех вершин}

if (color[i]=ColSubA) {Если она - неизбежная}

then

begin

write(' ',i); {Выводим ее}

inc(j); {Инкрементируем к-во неизбежных вершин}

Duty[j]:=i; {Запоминаем номер неизбежной вершины}

end;

writeln;

end;

Далее приводится полный текст решения задачи

program io96d2t4;

Const

White = 1;

Gray = 2;

ColSubA = 4;

var

A : array [0..101,0..101] of integer;

Color,Q,Duty : array [0..100] of integer;

N,i,j,subA,SubB,BegQ,EndQ,k : longint;

Procedure Put(x:longint);

Begin inc(EndQ); Q[EndQ]:=x; end;

Procedure Get(var x:longint);

Begin x:=Q[BegQ]; inc(BegQ); end;

Procedure Sort;

var

m,min,rmin,k : longint;

begin

for m:=1 to j-2 do

begin

min:=a[i,m]; rmin:=m;

for k:=m+1 to j-1 do

if a[i,k]<min

then begin min:=a[i,k]; rmin:=k; end;

a[i,rmin]:=a[i,m]; a[i,m]:=min;

end;

end;

Procedure Inputdata;

begin

i:=0; j:=1; read(a[0,1]);

while (a[i,j]<>-1) do

begin

while(a[i,j]<>-2) do

begin inc(j); read(a[i,j]) end;

if j >2 then Sort;

readln;

inc(i); j:=1; read(a[i,j]);

end;

N:=i;

end;

procedure OutSubA;

begin

SubA:=subA-2; write(subA); j:=0; Duty[0]:=0;

for i:=1 to N-1 do

if (color[i]=ColSubA)

then begin write(' ',i); inc(j); Duty[j]:=i; end;

writeln;

end;

procedure BFS;

var i,j : longint;

begin

for i:=0 to N do color[i]:=WHITE;

for i:=0 to N do Q[i]:=0;

color[0]:=GRAY; SubA:=0; BegQ:=1; EndQ:=0;

Put(0);

while (BegQ<=EndQ) do

begin

Get(i);

if BegQ>EndQ

then begin inc(SubA); Color[i]:=ColSubA end;

j:=1;

while (a[i,j]>=0) do

begin

if color[a[i,j]]=WHITE

then begin

Put(a[i,j]);

color[a[i,j]]:=GRAY;

end;

inc(j);

end;

end;

end;

Procedure OutSubB;

begin

SubB:=0;

for i:=1 to SubA do

if Duty[i]<>0 then inc(SubB);

write(subB);

for i:=1 to SubA do

if Duty[i]<>0 then write(' ',Duty[i]);

writeln;

end;

Procedure DelArcs(k:longint);

begin

for j:=N Downto 1 do a[k,j+1]:=a[k,j];

a[k,1]:=-2;

for i:=0 to N-1 do

begin

j:=1;

while (a[i,j]>=0) do

begin

if a[i,j]=k then a[i,j]:=maxint;

inc(j);

end;

end;

end;

Procedure RetArcs(k:longint);

begin

for i:=0 to N-1 do

begin

j:=1;

while (a[i,j]>=0) do

begin

if a[i,j]=maxint then a[i,j]:=k;

inc(j);

end;

end;

for j:=1 to N do a[k,j]:=a[k,j+1]

end;

begin

assign(input,'input.txt'); reset(input);

assign(output,'output.txt'); rewrite(output);

InputData;

BFS; {Поиск в ширину - находим "неизбежные" точки}

OutSubA;

for k:=1 to SubA do

begin

DelArcs(Duty[k]); BFS; RetArcs(Duty[k]);

for i:=0 to N-1 do

begin

j:=1;

while (a[i,j]>=0) do

begin

if (color[i]=WHITE) and (color[a[i,j]]<>WHITE)

then begin Duty[k]:=0; break end;

inc(j);

end;

end;

end;

OutSubB;

close(input); close(output);

end.

6. О размерностях использованных в задачах массивов

Заключение

- поиска кратчайших расстояний расстояний между всеми парами вершин графа (одновременно можно построить и сами кратчайшие пути от каждой вершины до каждой)

- построения матрицы достижимости графа

- построения множества истоков и множества стоков (исток - вершина, в которую нет входящих дуг) (сток - вершина, из которой нет исходящих дуг)

- метод Дейкстра, применяется для

- поиска кратчайших расстояний от одной вершины до всех остальных

- построения оптимальных маршрутов от одной вершины до всех остальных

- поиск в глубину, применяется для

- решения произвольных задач на графах, требующих соответствующего порядка обхода ("в глубину") графа;

- построения множества истоков и стоков (как истоков на транспонированном графе)

- построения сильносвязных компонент (ССК) графа ССК - это множество вершин, каждая из которых достижима из всех вершин ССК

- поиск в ширину, применяется для

- решения произвольных задач на графах, требующих соответствующего порядка обхода ("в ширину") графа;

Литература

1. М. Долинский "Памятка участнику олимпиады по информатике среди школьников", "Радиолюбитель. Ваш компьютер", Минск, No 1, 2000 с.20-21.

2. М. Долинский "Начинаем программировать самостоятельно", "Радиолюбитель. Ваш компьютер", Минск, No 1, 2000, с.23-24, No 2, 2000, с.22-23, No 3, 2000, с.23-25, No 4, 2000, с.26-27, No 5, с.27-28, No 6, с.23-26.

3. М. Долинский "Решение задач на тему "Геометрия на плоскости", "Радиолюбитель. Ваш компьютер", Минск, 2000, No 8, с.21-23, 2000, No 9, с.19-21.

4. М. Долинский "Разработка программ с использованием определяемых программистом типов данных", "Радиолюбитель. Ваш компьютер", Минск, 2001, No 1, 2001, с.29-31, No 3, с. 26-28.

5. М. Долинский " Решение задач с помощью очереди и стека" , Минск, "Радиолюбитель. Ваш компьютер", No 4, 2001, с.26-27, No 5, с.27-28, No 6, с.24-25.

6. М. Долинский " Обзор возможностей языка программирования Паскаль", Москва, Радиомир. Ваш компьютер", No 7, 2001, с.23-25.

7. М. Долинский "Алгоритмы генерации комбинаторных объектов" "Радиолюбитель. Ваш компьютер", (принята к публикации).

8. М. Долинский "Некоторые факты из теории чисел" "Радиолюбитель. Ваш компьютер", (принята к публикации).

9. М. Долинский "Использование рекурсивных функций и процедур" "Радиолюбитель. Ваш компьютер", (принята к публикации).

10. М. Долинский "Решение задач с помощью рекуррентных соотношений" "Радиолюбитель. Ваш компьютер", (принята к публикации).

11. Котов В.М., Волков И.А., Харитонович А.И. "Методы алгоритмизации" Учебное пособие для 8-го класса общеобразовательной школы с углубленным изучением информатики, Мн., "Народная асвета", 1996, 127 с.

12. Котов В.М., Волков И.А., Лапо А.И. "Методы алгоритмизации" Учебное пособие для 9-го класса общеобразовательной школы с углубленным изучением информатики, Мн., "Народная асвета", 1997, 160 с.

13. Котов В.М., Мельников О.И. "Методы алгоритмизации" Учебное пособие для 10-11-го классов общеобразовательной школы с углубленным изучением информатики, Мн., "Народная асвета", 2000, 221 с.