Часто в задачах встречается следующая конструкция - есть дома
и дороги, их соединяющие; у каждой дороги есть длина. По другой
терминологии такая конструкция называется графом, дома называются
"вершинами", дороги - "ребрами" или "дугами", а длина дороги -
"весом ребра" или "весом дуги". Таким образом фраза 'Найти мини-
мальный вес пути между вершинами s и k в графе' может быть переве-
дена так: 'Есть дома и дороги их соединяющие. Также заданы длины
дорог. Найти кратчайшую длину пути от города s до города k, если
двигаться можно только по дорогам'. Пропускная способность дуги
(i,j) означает, например, сколько груза может быть перевезено по
дороге (по дуге) (i,j) за единицу времени); а поток по дуге (i,j)
-- это сколько перевозится сейчас на самом деле).
Часто используют следующие обозначения: Г(x(i))- множество
вершин, в которые есть дуга из вершины i; Д(x(i))- множество вер-
шин, из которых есть дуга в вершину i.
Пусть в графе N вершин.
Длины дуг обычно заносятся в матрицу (назовем ее C) размера N
на N, называемой матрицей смежности:
var С: array [1..N,1..N] of integer;
Элемент C[i,j] этой матрицы равен длине дуги (дороги>), сое-
диняющей вершины i и j, и равен (например) 0 или -1, если такой
дуги нет. Если дорога двунаправленная (дуга неориентированная), то
очевидно, что C[i,j]=C[j,i].
А. Расстановка пометок. Вершина может находиться в одном из
трех состояний: вершине приписана пометка и вершина просмотрена (
т.е. она имеет пометку и все смежные с ней вершины "обработаны"),
пометка приписана, но вершина не просмотрена ( т.е. она имеет по-
метку, но не все смежные с ней вершины обработаны), вершина не
имеет пометки. Пометка произвольной вершины x(i) состоит из двух
частей и имеет один из двух видов: (+x(j),m) или (-x(j),m). Часть
+x(j) пометки первого типа означает, что поток допускает увеличе-
ние вдоль дуги (x(j),x(i)). Часть -x(j) пометки другого типа озна-
чает, что поток может быть уменьшен вдоль дуги (x(i),x(j)). В обо-
их случаях m задает максимальную величину дополнительного потока,
который может протекать от s к x(i) вдоль построенной увеличиваю-
щей цепи потока. Присвоение пометки вершине x(i) соответствует на-
хождению увеличивающей цепи потока от s к x(i). Сначала все верши-
ны не имеют пометок.
Шаг 1. Присвоить вершине s пометку (+s,m(s)=бесконечность).
Вершине s присвоена пометка и она просмотрена, все остальные вер-
шины без пометок.
Шаг 2. Взять некоторую непросмотренную вершину с пометкой;
пусть ее пометка будет (+-x(k),m(x(i))) (+- обозначает, что перед
x(k) может стоять как плюс, так и минус).
(I) Каждой помеченной вершине x(j), принадлежащей Г(x(i)),
для которой c(i,j)<q(i,j), присвоить пометку (-x(i),m(x(j))), где
m(x(j))=min[m(x(i)),q(i,j)-c(i,j)].
(II) Каждой непомеченной вершине x(j), принадлежащей Д(x),
для которой c(i,j)>0, присвоить пометку (-x(i),m(x(j))), где
m(x(j))=min[m(x(i)),c(j,i)].
(Теперь вершина x(i) и помечена, и просмотрена, а вершины x(j),
пометки которым присвоены в (I) и (II), являются непросмотренны-
ми.) Обозначить каким-либо способом, что вершина x(i) просмотрена.
Шаг 3. Повторять шаг 2 до тех пор, пока либо вершина t будет
помечена, и тогда перейти к шагу 4, либо t будет не помечена и ни-
каких других пометок нельзя будет расставить; в этом случае алго-
ритм заканчивает работу с максимальным вектором потока c. Здесь
следует отметить, что если X(0)-множество помеченных вершин, а
X'(0) - множество не помеченных, то ( X(0) --> X'(0) ) является
минимальным разрезом.
Б. Увеличение потока.
Шаг 4. Положить x=t и перейти к шагу 5.
Шаг 5. (I) Если пометка в вершине x имеет вид (+z,m(x)), то
изменить поток вдоль дуги (z,x) c c(z,x) на c(z,x)+m(t). (II) Если
пометка в вершине x имеет вид (-x,z) c c(x,z) на c(x,z)-m(t).
Шаг 6. Если z=s, то стереть все пометки и вернуться к шагу 1,
чтобы начать расставлять пометки, но используя уже улучшенный по-
ток, найденный на шаге 5. Если z<>s, то взять x=z и вернуть к шагу
5.
Обозначения: Г(x(i))- множество вершин, в которые есть дуга
из вершины i; Д(x(i))- множество вершин, из которых есть дуга в
вершину i; c(i,j) - это пропускная способность дуги (т.е., напри-
мер, сколько груза может быть перевезено по дороге (по дуге) (i,j)
за единицу времени); q(i,j) - поток по дуге (i,j) (т.е. сколько
перевозится сейчас на самом деле).
--------------------------------------
Обозначения:
C[i,j]- длина ребра(i,j), С[i,j]>=0 (если ребра нет, то его
длина полагается равной бесконечности).
D[i]- кратчайшее текущее расстояние от вершины нач до вершины
i.
флаг[i]- информация о просмотре вершины i: 0 - если вершина
не просмотрена, 1 - если просмотрена. Если вершина просмотрена, то
для нее D[i] есть наикратчайшее расстояние от вершины нач до вер-
шины i.
предок[i]- информация о номере вершины, предшествующей верши-
не i в кратчайшем пути от вершины нач.
минрас - это минимальное расстояние.
Алгоритм:
для i от 1 до N выполнять
нц
предок[i]:=нач;
флаг[i]:=0;
D[i]:=C[нач,i]
кц
флаг[нач]:=1; { пока мы знаем только расстояние }
предок[нач]:=0 { от вершины нач до нее же, равное 0 }
для i от 1 до N-1 выполнять
нц
минрас:=бесконечность;
для j от 1 до N выполнять
если (флаг[j]=0 и (минрас > D[j]) { находим минимальное}
то минрас:=D[j]; {расстояние}
k:=j; { до непомеченных вершин }
все
флаг[k]:=1; { вершина k помечается просмотренной }
для j от 1 до N выполнять { выполняем просмотр }
если флаг[j]=0 и D[j]>D[k]+C[k,j]
{ Т.е. если для вершины j еще не найдено кратчайшее
расстояние от нач, и из вершины k по дуге C[k,j]
путь в j короче, чем найденный ранее }
то D[j]:=D[k]+C[k,j] { то запоминаем его }
предок[j]:=k;
все
кц
Задача 1.
Задан набор неповторяющихся пар (Ai,Aj), Ai, Aj принадлежат
множеству А={A1, A2, ..., An}. Необходимо составить цепочку макси-
мальной длины по правилу
(Ai,Aj)+(
При образовании этой цепочки любая пара может быть использо-
вана не более одного раза.
Задача 2.
Между N пунктами (N<=50) заданы дороги длиной A(i,j), где
I,J-номера пунктов. Дороги проложены на разной высоте и пересека-
ются только в общих пунктах. В начальный момент времени из задан-
ных пунктов начинают двигаться с постоянной скоростью M роботов
(M=2 или 3), независимо меняя направление движения только в пунк-
тах. Роботы управляются таким образом, чтобы минимизировать время
до встречи всех роботов в одном месте. Скорость I-того робота мо-
жет быть равна 1 или 2 . Остановка роботов запрещена.
Задание:
Написать программу, которая:
1) при заданных N,M и сети дорог единичной длины (все имеющиеся
A(i,j)=1) определяет минимальное время, через которое может
произойти встреча всех M роботов, при этом начальное положение
роботов и скорость их движения известны.
2) Выполнить те же действия, что и в п. 1, но только для различных
значений A(i,j).
Примечание: В случае невозможности встречи всех M роботов в одном
месте ни в какой момент времени в результате выполнения программы
должно быть сформировано соответствующее сообщение.
Требование к вводу-выводу:
1) Все входные данные - целые неотрицательные числа;
2) при задании сети дорог должно быть указано количество дорог - K
и пункты их начала и конца в виде пар (i,j).
Задача 3.
На плоскости расположено N точек. Имеется робот, который дви-
гается следующим образом. Стартуя с некоторой начальной точки и
имея некоторое начальное направление, робот движется до первой
встреченной на его пути точки, изменяя в ней свое текущее направ-
ление на 90 градусов, т.е. поворачивая налево или направо. После
этого он продолжает движение аналогично. Если робот достиг началь-
ной точки, либо не может достичь новой точки (которую он еще не
посещал), то он останавливается.
Определить, может ли робот посетить все N точек, если:
1. Определены начальные точка и направление робота.
2. Определена начальная точка, а направление робота можно выби-
рать.
3. Начальную точку и направление робота можно выбирать.
Координаты точек - целые числа, угол измеряется в радианах
относительно оси ОХ.
Задача 4.
"ПУТЬ".
Найти кратчайшее расстояние между двумя вершинами в графе.
Найти все возможные пути между этими двумя вершинами в графе не-
пеpесекающиеся по
а) pебpам
б) веpшинам.
Задача 5.
Лабиринт задается матрицей смежности N*N, где C(i,j)=1, если
узел i связан узлом j посредством дороги. Часть узлов назначается
входами, часть - выходами. Входы и выходы задаются последователь-
ностями узлов X(1),..,X(p) и Y(1),..,Y(k) соответственно.
Найти максимальное число людей, которых можно провести от
входов до выходов таким образом, чтобы:
а) их пути не пересекались по дорогам, но могут пеpесекаться по узлам;
б) их пути не пересекались по узлам;
Задача 6.
N шестеpенок пpонумеpованы от 1 до N (N<= 10). Заданы M (0<=
<=M<=45) соединений паp шестеpенoк в виде (i,j), 1<=i<j<=N
(шестеpня с номеpом i находится в зацеплении с шестеpней j). Можно
ли повеpнуть шестеpню с номеpом 1?
Если да, то найти количество шестеpен, пpишедших в движение.
Если нет, то тpебуется убpать минимальное число шестеpен так,
чтобы в оставшейся системе пpи вpащении шестеpни 1 во вpащение
пpишло бы максимальное число шестеpен. Указать номеpа убpанных
шестеpен ( если такой набоp не один, то любой из них ) и количест-
во шестеpен, пpишедших в движение.
Задача 7.
На фигуре 1.показана вычислительная система,содержащая доста-
точное количество процессоров,использующих общую память из 26
числовых переменных A,B,C,....,Z. Система работает шагами. На каж-
дом шаге, каждый процессор выполняет либо оператор присваивания
либо пустой оператор. Оператор присваивания - это конструкция вида
(переменная)=(арифметическое выражение)
где арифметическое выражение без скобок и содержит не более 2 пе-
ременных и арифметические операции. Процессоры вычисляют выражения
и присваивают их значения переменным из левых частей операторов, а
потом приступают к следующим операторам (при том одновременно). Не
допускается одновременное выполнение 2 или больше операторов
присваивания с одинаковой левой частью. Пустой оператор обозначаем
символом &. Выполняя его, процессор простаивает 1 шаг.
┌──┐ ┌──┐ ┌──┐
│P1│ │P2│ ... │Pn│ ...
└┬─┘ └┬─┘ └┬─┘
│ │ │
┌───┴─────────┴──────────────┴───────────┐
├───┬───┬───┬────────────────────────┬───┤
│ A │ B │ C │ │ Z │
└───┴───┴───┴────────────────────────┴───┘
фиг. 1
n последовательности операторов (присваивания или пустых) с одина-
ковой длиной L называем n-программой с длиной L (выполняется за L
шагов на первых n процессоров), если на каждом шаге имеем не более
1 оператора с заданной левой частью. n-программы P и Q называем
эквивалентными, если начиная с одного и того же начального состоя-
ния переменных A,B,...,Z после выполнения как P, так и Q получа-
ется одинаковый результат.
Напишите программу,которая:
Задание 1. Вводит целое k(k<25) и 1-программу, содержащую k
операторов присваивания.
Задание 2. Проверяет правильность введенных операторов.
Задание 3. Преобразует 1-программу в эквивалентную m-програм-
му c минимальной длиной (добавляя если надо пустые операторы) и
выводит полученный результат.
Задание 4. Не увеличивая длину построенной в Задании 3
n-программы, преобразует ее в эквивалентную m-программу, m-как
можно меньше, и выводит полученный результат.
Замечание. На фигуре 2 показана 1-программа из 6 операторов и
3-программа и 2-программа - возможные решения задач 3(б) и 4(в).
а) D=A*D б) A=B+C B=C+D D=D-E
A=B+C A=A-E & &
A=A-E E=A*B D=A*D &
B=C+D в) A=B+C B=C+D
D=D-E A=A-E D=D-E
E=A*B E=A*B D=A*D
фиг.2.
Задача 8.
Имеется N прямоугольных конвертов и N прямоугольных открыток
различных размеров. Можно ли разложить все открытки по конвертам,
чтобы в каждом конверте было по одной открытке. Замечание. Открыт-
ки нельзя складывать, сгибать и т.п., но можно помещать в конверт
под углом. Например, открытка с размерами сторон 5:1 помещается в
конверты с размерами 5:1, 6:3, 4.3:4.3, но не входит в конверты с
размерами 4:1, 10:0.5, 4.2:4.2.
Задача 9.
Составить программу для нахождения произвольного разбиения 20
студентов на 2 команды, численность которых отличается не более
чем в 2 раза, если известно,что в любой команде должны быть сту-
денты, обязательно знакомые друг с другом. Круг знакомств задается
матрицей (20,20) с элементами
A(ij)={1,если i студент знаком с j
{0,иначе .
Задача 10.
Имеется N человек и прямоугольная таблица А[1:N,1:N];элемент
A[i,j] равен 1, если человек i знаком с человеком j, А[i,j] =
=А[j,i]. Можно ли разбить людей на 2 группы, чтобы в каждой группе
были только незнакомые люди.
Задача 11.
На олимпиаду прибыло N человек. Некоторые из них знакомы меж-
ду собой.Можно ли опосредованно перезнакомить их всех между собой?
(Незнакомые люди могут познакомиться только через общего знакомо-
го).
Задача 12.
Пусть группа состоит из N человек. В ней каждый имеет (N/2)
друзей и не больше K врагов. У одного из них есть книга, которую
все хотели бы прочитать и потом обсудить с некоторыми из осталь-
ных.
Написать программу, которая:
1. Находит способ передачи книги таким образом,чтобы она по-
бывала у каждого в точности один раз,переходя только от друга к
другу и наконец возвратилась к своему владельцу.
2.Разбивает людей на S групп, где будет обсуждаться книга,
таким образом, чтобы вместе с каждым человеком в ту же самую груп-
пу вошло не более P его врагов.
Примечание: предполагается, что S*P>=K.
Задача 13.
В заданном графе необходимо определить, существует ли цикл,
проходящий по каждому ребру графа ровно один раз.
Задача 14.
Следующая фигура показывает запутанную сеть дорог района го-
рода. Представьте, что мусорная машина должна пройти по всем доро-
гам хотя бы один раз, чтобы собрать мусор. Число на каждой стороне
показывает время, которое должна потратить мусорная машина, чтобы
проехать этот интервал. На перекрестках машина должна ждать время,
равное числу пересекающихся дорог.
Составьте программу, показывающую как выбрать необходимый
путь для сбора мусора в кратчайшее время.
│ 10 │
───O┌─────────────────────┐O───
│└────┐4 8┌───┘│
8 │ 4 └─────┬──────┘ 7 │ 6
───O┌──────────O───────────O───
│└────┐ 10 │
7 │ 7 └─────┐ 8 │ 8
───O───────────O───────────O───
│ 11┌─────┼──────┐5 │
6 │┌────┘ 4│ └───┐│ 13
───O└──────────O──────────┘O───
│ 12 │ 9 │
│ │
Есть 11 остановок.
от 1 до 2 путь 10 мин.
от 1 до 3 4
от 1 до 4 8
от 2 до 3 8
от 2 до 5 6
от 3 до 4 4
от 3 до 5 7
от 4 до 7 7
от 4 до 6 10
от 4 до 8 7
от 8 до 6 7
от 8 до 10 6
от 10 до 6 11
от 6 до 9 4
от 10 до 9 12
от 6 до 11 5
от 6 до 4 8
от 5 до 4 8
от 4 до 11 13
от 9 до 11 5
Задача 15.
N pазличных станков один за дpугим объединены в конвейеp.
Имеется N pабочих. Задана матpица C[N , N], где C[i,j] пpоизводи-
тельность i-ого pабочего на j-ом станке. Опpеделить
а) на каком станке должен pаботать каждый из pабочих, чтобы
пpоизводительность была максимальной.
б) то же, но станки pасположены паpаллельно и выполняют од-
ноpодные опеpации.
Задача 16.
На плоскости задан граф с N вершинами. Количество ребер, сое-
диненных с каждой вершиной, равно 3.
Пример:
B┌────────────┐C
│\ /│
│ \ G F / │
│ ┌──────┐ │
│ │ │ │
│ │ │ │
│ └──────┘ │
│ / H E\ │
│ / \ │
A└────────────┘D
Пусть вершины X,Y и Z являются соседями вершины Т. Будем счи-
тать, что Y левый, а Z -правый сосед вершины Т относительно верши-
ны X, если ориентированный угол XTZ меньше ориентированного угла
XTY (положительным будем считать направление против часовой стрел-
ки). Например вершина Е является правым соседом вершины Н относи-
тельно А, а G - левым, поскольку ориентированный угол АНЕ меньше
ориентированного угла AHG. (Ребра считаются отрезками).
Составьте программу, которая:
1. Вводит координаты вершин графа и его ребра и рисует граф на
экране компьютера,производя при этом подходящее масштабирова-
ние(Ребра выводятся как отрезки).
2. Пусть заданы две начальные соседние вершины XO и X1 и после-
довательность вида LLRRL... Тогда программа находит путь на графе
XOX1X2...Xn для вершин которого выполнено:
-первые два являются заданными XO и X1
-Xi+1 является левым или правым соседом Xi относительно Xi-1 в
зависимости от заданной последовательности,при том L означает ле-
вый, а R -правый.
Пример:В заданном графе пусть даны начальные вершины А и H и
последовательность LRRLLR. Тогда программа должна найти путь
AHGFEDCB.
3. Рисует на экране путь,найденный в п.2.
4. Пусть даны начальная и конечная вершина. Программа должна
найти путь,проходящий через минимальное число вершин, вывести его
на экран и найти 2 первые вершины и управляющую последовательность
для этого пути, как определено в п.2.
Задача 17.
Имеется N городов. Для каждой пары городов (I,J) можно пост-
роить дорогу, соединяющую эти два города и не заходящие в другие
города. Стоимость такой дороги A(I,J). Вне городов дороги не пе-
ресекаются.
Написать алгоритм для нахождения самой дешевой системы до-
рог, позволяющей попасть из любого города в любой другой. Резуль-
таты задавать таблицей B[1:N,1:N], где B[I,J]=1 тогда и только
тогда, когда дорогу, соединяющую города I и J, следует строить.
Задача 18.
В картинной галерее каждый сторож работает в течение некото-
рого непрерывного отрезка времени. Расписанием стражи называется
множество пар [Т1(i), Т2(i)] - моментов начала и конца дежурства
i-го сторожа из интервала [0,EndTime].
Для заданного расписания стражи требуется:
(а) проверить, в любой ли момент в галерее находится не менее двух
сторожей.
Если условие (а) не выполнено, то:
(б) перечислить все интервалы времени с недостаточной охраной (ме-
нее 2 сторожей).
(в) добавить наименьшее число сторожей с заданной, одинаковой для
всех длительностью дежурства, чтобы получить правильное
расписание (т.е. удовлетворяющее условию (а)).
(г) проверить, можно ли обойтись без добавления новых сторожей,
если разрешается сдвигать времена дежурства каждого из сторо-
жей с сохранением длительности дежурства.
(д) Если это возможно, то составить расписание с наименьшим числом
сдвигов.
ВХОДНЫЕ ДАННЫЕ:
(Все моменты времени задаются в целых минутах.)
EndTime - момент окончания стражи, т.е. охраняется отрезок времени
[0, EndTime].
N - число сторожей.
T1[i], T2[i], i=1,..N - моменты начала и окончания дежурства i-го
сторожа.
Length - длительность дежурства каждого дополнительного сторожа.
ВЫХОДНЫЕ ДАННЫЕ:
(1) Ответ на пункт (а) в форме да/нет.
(2) При ответе "нет" на п. (а) - список пар (k,l) - начал и концов
всех малоохраняемых интервалов с указанием числа сторожей в
каждом (0 или 1).
(3) Число дополнительных сторожей и моменты начала и окончания де-
журства каждого дополнительного сторожа.
(4) Ответ на пункт (г) в форме да/нет. Если "да", то номера сторо-
жей, смена которых сдвигается, и значения сдвигов.
(5) В ответ на пункт (д): наименьшее число сторожей, смена которых
сдвигается, их номера и значения сдвигов.
ПРИМЕЧАНИЕ
Программа должна допускать независимое тестирование пунктов (в),
(г), (д).
Задача 19.
Вводится N - количество домов и К - количество дорог. Дома
пронумерованы от 1 до N. Каждая дорога определяется тройкой чисел
- двумя номерами домов - концов дороги и длиной дороги. В каждом
доме живет по одному человеку. Найти точку - место встречи всех
людей, от которой суммарное расстояние до всех домов будет мини-
мальным.
Если точка лежит на доpоге, то указать номера домов - концов
этой доpоги и расстояние от первого из этих домов. Если точка сов-
падает с домом, то указать номер этого дома.
Примечание: длины дорог - положительные целые числа.
Задача 20.
N колец сцеплены между собой (задана матрица A(n*n), A(i,j)=1
в случае, если кольца i и j сцеплены друг с другом и A(i,j)=0 ина-
че). Удалить минимальное количество колец так, чтобы получилась
цепочка.
Задача 21.
Янка положил на стол N выпуклых K-гранников и N различных ти-
пов наклеек по K штук каждая. Ночью кто-то наклеил наклейки на
грани, по одной на грань.
Помогите Янке расставить многогранники так, чтобы наклейка
каждого типа была видна pовно K-1 раз.
Задача 22.
Имеется N точек и M проводков. Проводком можно соединить не-
которую пару различных точек, причем пара может быть соединена не
более чем одним проводком. Все проводки должны быть использованы.
Пусть Di - количество проводков, которые будут соединены с
точкой с номером i, i=1, ..., N.
Необходимо соединить N точек с помощью M проводков таким обра-
зом, чтобы сумма S=D1*D1 + D2*D2 + ... + Dn*Dn была максимальной.
Вывести величины Di в неубывающем порядке и. по требованию
(priznak=1), список соединений.
ВВОД:
<Введите N:> N (N<=100)
<Введите M:> M (M<=1000)
<PRIZNAK=> PRIZNAK
ВЫВОД:
<Результирующая конфигурация:> Di в неубывающем порядке.
<Сумма S> S
<Список соединений>
<Точку 1 соединить с> список точек
.....
<Точку N соединить с> список точек
Задача 23.
Задано N городов c номерами от 1 до N и сеть из M дорог с од-
носторонним движением между ними. Каждая дорога задается тройкой
(i, j, k), где i - номер города, в котором дорога начинается, j -
номер города, в котором дорога заканчивается, а k - ее длина
(число k - натуральное). Дороги друг с другом могут пересекаться
только в концевых городах.
Все пути между двумя указанными городами A и B можно упорядо-
чить в список по неубыванию их длин (если есть несколько путей
одинаковой длины, то выбираем один из них). Необходимо найти один
из путей, который может быть вторым в списке.
Вывести его длину L и города, через которые он проходит.
ВВОД:
<Количество городов N:> N
<Количество дорог M:> M
<Начало, конец и длина дороги 1:> i1, j1, k1
......
<Начало, конец и длина дороги M:> iM, jM, kM
<Города A и B, между которыми надо найти путь:> A, B
ВЫВОД:
<Пути нет>
или
<Путь проходит по городам> A, i1, i2, ..., B
<Длина пути> L
Задача 1.
Для более удобного хранения информации заведем матрицу
C[1...n,1..n] (так называемую матрицу смежности) в которой
C[i,j]=1, если в наборе есть пара (Ai,Aj) и C[i,j]=0 иначе.
Будем строить все возможные цепочки (по правилу, данному в
условии) и искать среди них ту, которая имеет максимальную длину.
В качестве начального символа цепочки можно взять любой сим-
вол из A. Пусть это символ Ai. Ищем, просматривая строку i матрицы
C слева направо элемент C[i,j]=1 (другими словами, ищем пару с
первым элементом Ai). Если такого элемента не существует, то берем
в качестве начала строки другой элемент множества A. Если элемент
C[i,j]=1 найден, то ему соответствует пара (Ai,Aj). Помечаем ее
как уже использованную полагая, например, C[i,j]=-1. Далее
просматриваем слева направо строку j матрицы C в поисках еще не
использованной пары (Aj,Ak) (C[j,k]=1). Присоединяем элемент Ak к
имеющейся цепочке, полагаем C[j,k]=-1, ищем единичный элемент в
строке k и т.д. Предположим, на некотором шаге мы получили цепочку
Ai
и в строке p матрицы больше нет ни одного единичного элемента. Это
означает, что при таком подборе предыдущих элементов мы нашли
максимальную по длине строку. Если ее длина больше длин всех най-
денных ранее строк, запоминаем эту строку как рекорд. После этого
"отщепляем" от строки последний элемент Ap и смотрим, есть ли еще
в строке l единичный элемент с индексом, большим p. Если да, то
приписываем уже этот элемент к строке и пытаемся затем снова уве-
личить длину полученной строки, если же нет, то "отщепляем" от
строки элемент Al, в строке S ищем единичный элемент с индексом,
большим l и т.д.
Останов осуществляется тогда, когда мы должны "отщепить" от
строки Ai.
Перебираем цепочки, начинающиеся со всех возможных элементов
множества A. Находим строку максимальной длины:
const M=10; { максимально число элементов в A }
{ будем считать, что A состоит из чисел от 1 до N }
var c:array[1..M,1..M] of integer;
curstr, maxstr: array[0..M] of integer;
{ в этих переменных хранятся текущая цепочка и }
{ цепочка максимальной длины. }
{ В нулевом элементе хранится длина цепочки }
N,E : integer; { N - число элементов в A }
i,j,k : integer; { E - число пар в наборе }
procedure find;
var l,j : integer;
begin
l:=curstr[curstr[0]]; { l = последний элемент цепочки }
for j:=1 to N do { просмотр строки l }
if C[l,j]=1
then begin
curstr[0]:=curstr[0]+1;
curstr[curstr[0]]:=j; { j -> в цепочку }
c[l,j]:=-1; { пара использована }
find;
c[l,j]:=1; { пару снова разрешено }
{ использовать }
curstr[0]:=curstr[0]-1;
end;
if curstr[0]>maxstr[0] { если нашли более }
then maxstr:=curstr { длинную строку }
end;
begin
readln(N); readln(E);
for i:=1 to N do
for j:=1 to N do
C[i,j]:=0;
for k:=1 to E do begin
write('очередная пара: ',i,j);
c[i,j]:=1
end;
for i:=1 to N do begin
curr[0]:=1; { поиск цепочки }
curr[1]:=i; { начинающейся элементом i }
find;
end;
for i:=1 to maxstr[0] do
write(maxstr[i]); { печать максимальной строки }
end.
Задача 2.
Для решения задачи важно понять, что встреча роботов может
произойти либо в пункте, либо на дороге. В первом случае задача
решается просто: необходимо последовательно строить множества
пунктов для каждого робота, в которых они могут оказаться через
время, равное 0.5,1,1.5,2,...Т. Это можно делать, используя очере-
ди. В случае же встречи роботов на дороге легко понять, что не-
посредственно перед встречей все они должны были находится в сле-
дующих пунктах:
1. Либо в двух пунктах, связанных дорогой;
2. Либо в пунктах, из которых есть дороги в один и тот же
пункт;
3. Либо в трех пунктах, образующих треугольник.
Поэтому, после каждого целого такта времени, достаточно про-
верять, находятся ли роботы в одной из описанных 3 ситуаций. При
этом время подсчитывается очевидным способом.
Задача 3.
Рассмотрим только случай, когда роботы двигаются только па-
раллельно координатным осям, в других случаях можно сделать преоб-
разование координат.
Легко понять, что если рассмотреть точку, имеющую наибольшую
координату Y, причем самую левую (т.е. наименьшую координату Х,
если таких несколько), то для нее существует только 2 возможность
быть пройденной роботом: робот должен прийти из ближайшей точки А
снизу и пойти в ближайшую точку Б справа или наоборот. В любом
случае эти 2 отрезка фиксированы для робота. Теперь те же рассуж-
дения можно провести и для точек Б и точки, находящейся правее Б,
а также для самых нижних, левых и правых точек. Окончательно полу-
чается, что возможный проход робота строго фиксирован. Если упоря-
дочить точки по горизонталям (вертикалям), то первая точка гори-
зонтали (вертикали) должна соединятся со второй, третья с четвер-
той и т.д. Понятно, что если получившаяся фигура связна (цикл), то
решение существует для случаев 2. и 3., а для случая 1. нужно про-
верить, в нужном ли направлении стоит робот. Однако есть одна
трудность в случае, когда существуют горизонталь и вертикаль, со-
держащие нечетное число точек, а обход существует. Это возможно
только в случае, когда это стартовая точка обхода, причем она на-
ходится в 'нечетной' горизонтали и вертикали. Удалив ее, можно
воспользоваться предыдущей процедурой, при этом фиксированные от-
резки не должны пересекаться в удаленной точке.
Задача 4.
Для решения задачи достаточно воспользоваться алгоритмом на-
хождения потока между двумя заданными вершинами, преобразуя в слу-
чае а) граф по следующему правилу: каждую вершину исходного графа
превращаем в ребро с пропускной способностью 1.
Задача 5.
Решается аналогично задаче 4.
Задача 6.
Будем обозначать вращение по часовой стрелке нулем, против -
единицей. Сначала припишем шестерне с номером 1 число нуль. На
следующем шаге всем шестерням, сцепленным с первой, будут приписа-
ны числа 1 (они будут вращаться в противоположную шестерне 1 сто-
рону). Далее всем шестерням, находящимся в зацеплении с занумеро-
ванными на предыдущем шаге, припишем значения 0 и и.т.д.
Процесс будем повторять до тех пор, пока либо на очередном
шаге ни одной шестерне не будет приписано новое значение, и тогда
шестерню с номером 1 удастся повернуть, и число рассмотренных
шестеренок и есть искомое число пришедших в движение, либо на ка-
ком-то шаге пометка шестерни изменяется с 1 на 0 или с 0 на 1, и
тогда система в движение не придет.
Перебирая сначала все возможные варианты выбрасывания по од-
ной, затем, в случае неудачи по две, три, ... ,N-1 шестерни и про-
водя аналогичные рассуждения мы получаем максимальное число шесте-
рен, которое могло бы прийти в движение. О генерации вариантов
выбрасывания шестерен см. задачу 2 (перебор).
Задача 8.
Можно сформировать граф, состоящий из 2*N вершин, соот-
ветствующих открыткам и конвертам, причем две вершины соединены
ребром, если одна соответствует открытке, а другая - конверту, при
этом соответствующая открытка входит в соответствующий конверт.
Добавив в этом графе 2 новые вершины, одна из которых смежна всем
вершинам, соответствующим открыткам, а другая - всем вершинам,
соответствующим конвертам, сведем задачу к задаче нахождения
максимального потока между этими вершинами.
Задача 9.
Разбиение на группы осуществляется аналогично, как и в Задаче
10. за тем исключением, что в ситуации 3. организуются две новые
группы (пара групп, одна из них может оказаться в результате
пустой). После разбиения всех людей будем использовать принцип
формирования двух результирующих групп, основываясь на идее реше-
ния Задачи 2 из главы "Сортировки", учитывая возможности об'едине-
ния двух пар групп в одну пару групп произвольным слиянием двух
групп из различных пар.
Задача 10.
Задача решается следующим образом. Выбирается произвольный
человек и помещается в первую группу. Затем находятся люди, ему
знакомые. Понятно, что они не могут находиться в первой группе,
поэтому их необходимо поместить во вторую. Затем находятся люди,
знакомые людям из второй группы. Понятно, что они не могут нахо-
диться во второй группе, поэтому их необходимо поместить в первую.
Повторяя так поочередно для каждой из групп, мы придем к одной из
ситуаций:
1. Какой-то человек сначала был помещен в одну группу, а по-
том должен быть помещен в другую. Понятно, что в этом случае
задача не имеет решения.
2. Каждый человек помещен в одну из групп. В этом случае за-
дача решена.
3. Не каждый человек помещен в одну из групп. Это означает,
что оставшиеся не помещенные в группы люди не знакомы людям в
группах (иначе они были бы куда-нибудь помещены). Следова-
тельно, одного из них безразлично куда помещать, например в
первую группу. Затем описанный выше процесс продолжается, по-
ка не придем к ситуации 1. или 2.
Задача 11.
Для решения задачи достаточно определить, является ли связным
граф, определяемый матрицей смежности, элементы которой а[i,j]
равны 1, если люди с номерами i и j знакомы и равны 0 иначе. Граф
называется связным, если существует путь между любыми парами его
вершин. Понятно, что путь между вершинами i и j в таком графе и
определяет возможную последовательность знакомств, позволяющих
познакомить людей с номерами i и j.
Для определения связности графа можно воспользоваться методом
поиска в ширину, который состоит в следующем.
На начальном этапе в очередь помещается некоторая начальная
вершина, например вершина с номером 1.
На каждой из следующих итераций (пока очередь не пуста) вы-
полняются следующие действия:
- извлекается вершина из очереди;
- определяются вершины, ей смежные и которые в очереди еще не
были, и помещаются в очередь.
Если в результате таких действий все вершины побывали в оче-
реди (а для этого удобнее подсчитывать количество вершин, там по-
бывавших), то граф связен, иначе не связен. Для маркировки вершин,
побывавших в очереди, можно использовать массив размера N с эле-
ментами 0 и 1.
Задача 12.
Задача может быть сформулирована в графовой постановке следу-
ющим образом: найти простой цикл в графе (т.е. без повторяющихся
вершин), проходящий через все вершины графа. В общем случае не су-
ществует эффективного алгоритма решения этой задачи. Однако в дан-
ном случае задачу можно решить эффективно.
Предположим, что уже построен некоторый простой путь
(x[1],x[2],...x[k]) Множество вершин, вошедших в путь, будем счи-
тать пройденными, остальные не пройденные. Возможны 3 ситуации.
1. Одна из вершин x[1],x[k] смежна одной из не пройденных еще
вершин. В этом случае путь можно очевидным образом удлинить на од-
ну вершину.
2. Ни одна из вершин x[1],x[k] не смежна одной из не пройден-
ных еще вершин, а вершины x[1] и x[k] смежны. В этом случае понят-
но, что k>N/2, так как вершины x[1] и x[k] смежны N/2 вершинам.
Следовательно количество не пройденных вершин не больше N/2. Сле-
довательно любая вершина у из них смежна одной из пройденных вер-
шин, например x[i]. Но тогда можно получить более длинный путь
(у,x[i],x[i+1],...,x[k],x[1],x[2],...x[i-1]).
3. В этом случае степеней вершин нетрудно показать, что в пу-
ти (x[1],x[2],...x[k]) существует такой индекс i, что x[1] смежна
x[i], а x[i-1] смежна x[k]. Следовательно, рассмотрев путь
(x[i],x[i+1],...,x[k],x[i-1],x[i-2],...x[1]) мы имеем ситуацию 2.,
поэтому можно получить более длинный путь.
Применяя описанный выше способ начиная с пути длины 1, пост-
роим простой цикл, включающий все вершины.
Задача 13.
В заданном графе необходимо определить, существует ли цикл,
проходящий по каждому ребру графа ровно один раз.
Для существования такого цикла необходимо и достаточно нали-
чия двух условий:
1. граф является связным;
2. степень любой вершины графа четна.
Первое условие очевидно. Второе следует из факта, что если такой
цикл существует и заходит в некоторую вершину графа, то он должен
и выйти из нее. Проверив эти условия (для проверки связности можно
воспользоваться алгоритмом для задачи 11).
Предположим, что некоторый цикл А (не обязательно проходящий
через все ребра графа) уже построен и из графа выброшены ребра
цикла (их можно просто отметить как пройденные). Найдем вершину
(пусть это вершина к), через которую этот цикл проходил, но кото-
рой инцидентны некоторые ребра (непройденные). Построим новый цикл
В, который начинается в вершине к, по следующему правилу.
Находясь в текущей вершине цикла ( вначале это вершина к),
находим непройденное еще ребро, инцидентное текущей вершине. Это
ребро и определяет новую текущую вершину цикла, а ребро считается
пройденным. Построение цикла В продолжается до тех пор, пока это
возможно. Легко понять, что это будет цикл, так как степень любой
вершины четна. Предположим, что построение цикла В завершено.
Склеиваем теперь циклы А и В следующим образом. Находим в цикле А
(последовательности вершин) вершину к и заменяем ее последователь-
ностью вершин цикла В.
Такой процесс повторяется до тех пор, пока все ребра не будут
пройдены. Описанный процесс можно начинать с пустого цикла А
(пустой последовательности).
Задача 14.
Так как сеть дорог определяет некоторый граф, то определим в
этом графе множество вершин с нечетной степенью. Понятно, что ко-
личество таких вершин четно (так как сумма степеней вершин графа
четна). Определим на этом множестве взвешенный граф (граф, на реб-
рах которого определены веса или расстояния) по следующему прави-
лу. Вес ребра (i,j) равен кратчайшему расстоянию между вершинами,
соответствующими i и j в исходном графе. Построим в этом графе со-
вершенное сочетание минимального веса. Паросочетанием называется
множество попарно несмежных ребер (не имеющих общих вершин). Па-
росочетание называется совершенным, если оно покрывает все верши-
ны. Весом паросочетания называется суммарный вес входящих в него
ребер. Существуют эффективные алгоритмы поиска совершенного соче-
тания минимального веса. Однако они очень трудны. Поэтому при ма-
лом количестве вершин в графе можно воспользоваться перебором всех
возможных совершенных паросочетаний. При добавлении к исходному
графу ребер совершенного паросочетания получится граф, у которого
все степени вершин четны. Найдем в нем цикл, проходящий по каждому
ребру графа ровно один раз. Этот цикл и является решением задачи.
Заметим при этом, что каждое ребро (i,j) паросочетания должно быть
заменено последовательностью дорог исходного графа, которая опре-
деляет кратчайшее расстояние между вершинами i и j в исходном гра-
фе.
Задача 15.
Производительность конвейера определяется минимальной произ-
водительностью рабочего на конвейере. Поэтому для решения задачи
нам достаточно определить максимальную производительность Р, при
которой возможно распределить по станкам, всех рабочих, когда для
каждого рабочего определен набор станков, на которые он может быть
поставлен (понятно, что это те станки, производительность на кото-
рых у рабочего не ниже производительности Р). Легко понять, что
для выбранной производительности Х задача определения, возможно ли
распределение по станкам для каждого рабочего, аналогична решению
задачи 4. Для определения максимальной производительности Р, при
которой возможно распределить по станкам всех рабочих, можно
воспользоваться методом дихотомии следующим образом. Отсортируем в
одномерном A массиве размера N*N все элементы C[i,j], 1<=i,j<=N.
Определим левую границу ЛГ=1 и правую границу ПГ=N.
Для элемента массива А с индексом СГ=(ЛГ+ПГ)/2, рассматривае-
мого в качестве возможной максимальной производительности Р, опре-
деляем, можно ли распределить по станкам всех рабочих. Если да, то
величина возможной максимальной производительности Р увеличива-
ется. Для этого пересчитывается значение левой границы по правилу
ЛГ:=СГ+1. Если нет, то величина возможной максимальной производи-
тельности Р уменьшается. Для этого пересчитывается значение правой
границы по правилу ПГ:=СГ-1.
Процесс заканчивается, когда ЛГ>=ПГ. Значение А[ПГ-1] и явля-
ется максимальной производительностью Р, а конкретное распределе-
ние рабочих определяется структурой максимального потока.
Задача 17.
Легко понять, что сеть дорог будет реализовывать некоторый
связный (так как можно проехать из любого города в любой) граф без
циклов (так как одно ребро из цикла можно выбросить, а связный
граф останется связным). Поэтому алгоритм построения сети дорог
минимальной суммарной стоимости очень прост. На каждой итерации
необходимо находить дорогу минимальной стоимости, которая не обра-
зует цикла с уже выбранными дорогами на предыдущих итерациях.
Основную трудность такого решения составляет проверка условия, об-
разуют ли ребра цикл.
Однако решение существенно упрощается, если рассматривать
только минимальные ребра только между двумя множествами: множест-
вом помеченных вершин и множеством непомеченных вершин. Понятно,
что эти множества должно соединять хотя бы одно ребро, чтобы граф
был связным. Ясно, что оно должно быть минимальным по длине. В
описываемом ниже алгоритме это делается следующим образом.
Для каждой вершины к из множества непомеченных вершин (а на
начальном этапе это все вершины, кроме первой) определяется бли-
жайшая вершина из множества помеченных вершин БЛИЖ[к]. На каждой
итерации определяется кратчайшее ребро (i,j) между множеством по-
меченных вершин и множеством непомеченных вершин, используя массив
БЛИЖ. Найденное ребро выбирается для системы дорог, а соответству-
ющая вершина j считается помеченной. После этого пересчитывается
массив БЛИЖ. При этом учитывается, что к изменение некоторой вели-
чины БЛИЖ[k] может произойти только тогда, когда расстояние от k
до j меньше, чем от k до БЛИЖ[k].
Алгоритм
для i от 1 до N выполнять
нц
флаг[i]:=0;
БЛИЖ[i]:=1
кц
флаг[1]:=1;
для k от 1 до N-1 выполнять
нц
минрас:=бесконечность;
для i от 2 до N выполнять
если флаг[i]=0 и минрас > C[БЛИЖ[i],i]
то минрас:=C[БЛИЖ[i],i];
j:=i;
все
Вывод ребра (БЛИЖ[j],j)
флаг[j]:=1;
для i от 2 до N выполнять
если флаг[i]=0 и C[БЛИЖ[i],i]>C[i,j]
то БЛИЖ[i]:=j;
все
кц
Задача 19.
Предположим, что мы нашли точку встречи z, и пусть она лежит
на дороге (u,v) длины l на расстоянии d>0 от дома u и на расстоя-
нии (l-d)>0 от дома v. Все множество домов разделим на два непе-
ресекающихся подмножества V и U. В подмножество U входят те дома,
расстояние от которых до дома v меньше, чем расстояние до дома u.
Все остальные дома отнесем к подмножеству U.
Пусть B подмножестве V домов Kv, а в U - Ku, и пусть Kv>Ku.
Обозначим суммарное расстояние от точки z (находящейся на
расстоянии d от дома u) до всех N домов через R(z,d). Очевидно,
что
R(z,d)= сумма расстояний от v до домов множества V +
+ сумма расстояний от u до домов множества U +
+ Ku*d + Kv*(L-d).
Если мы сдвинем z на расстояние p, p<(L-d) по направлению к
дому v, то
R(z,d+p)=R(z,d)+Ku*p+Kv*(-p)=
=R(z,d)+(Ku-Kv)p<R(z,d) ?!
т.е. первоначальная установка точки z была неверной. Случай
Kv<Ku рассматривается аналогично. Если же Kv=Ku, то точка z может
быть на дороге в любом месте, в том числе и в концевых домах.
Итак, из всего выше сказанного следует, что искомая точка
совпадает с одним из N домов, и что нам достаточно для каждого из
домов i вычислить (например, по алгоритму Дейкстры) кратчайшее
расстояние от него до каждого из оставшихся домов, затем найти
сумму этих кратчайших расстояний (т.е. минимальное суммарное
расстояние до всех домов от i). Минимальное из суммарных расстоя-
ний по всем i и даст решение задачи.
Задача 20.
Предполагаемый вариант решения использует полный перебор всех
вариантов. В качестве первого звена цепочки берем последовательно
каждое из N колец. Ищем сцепленные с этим кольцом, выбираем среди
них одно (все остальные кольца будут считаться удаленными - т.е.
строки и столбцы с номерами этих колец должны обнуляться). С этим
изменением задача сводится к задаче 1 (Графы). Действительно, если
мы найдем максимальный путь в графе (в данном случае - максималь-
ную длину цепочки в начальной конструкции), то мы минимизируем ко-
личество выброшенных колец.
Задача 21.
Можно сформировать граф, состоящий из 2*N вершин, соот-
ветствующих К-гранникам и типу наклеек, причем две вершины соеди-
нены ребром, если одна соответствует наклейке, а другая - К-гран-
нику, при этом наклейка соответствующего типа находится на соот-
ветствующем К-граннике. Добавив в этом графе 2 новые вершины, одна
из которых смежна всем вершинам, соответствующим типам наклеек, а
другая - всем вершинам, соответствующим К-гранникам, сведем задачу
к задаче нахождения максимального потока между этими вершинами.
Задача 22.
Показывается, что точное решение есть максимум из двух
решений, полученных при помощи следующих эвристик:
1) Вершину 1 соединяем последовательно с вершинами 2, 3,
..., N.
Вершину 2 соединяем последовательно с вершинами 3,4,...,N.
......
Вершину i соединяем последовательно с вершинами i+1, i+2,
...,N.
......
и так до тех пор, пока хватит проводков.
2) Вершину 2 соединяем с вершиной 1.
Вершину 3 соединяем последовательно с вершинами 1,2.
......
Вершину i соединяем последовательно с вершинами i-1, i-2,
...,1.
......
и так до тех пор, пока хватит проводков.
Задача 23.
Алгоритм нахождения второго минимального расстояния между
двумя вершинами:
По алгоритму Дейкстры находим кратчайший путь между начальной
вершиной N и конечной K, состоящий из дуг a1, ..., as. Во втором
по длине кратчайшем пути из N в K не будет по крайней мере одного
из ребер ai. Поэтому алгоритм нахождения этого второго пути будет
следующим:
Для i от 1 до s повторять
удалить из графа ребро (дорогу) ai;
найти кратчайший путь из N в K в новом графе;
если его длина меньше рекордной минимальной длины,
полученной ранее,
то запомнить текущий путь и его длину как рекорд;
восстановить в графе ребро (дорогу) ai;
конец_для;
Этот алгоритм можно найти в книге Кристофидеса "Теория графов. Ал-
горитмический подход". Но в нем не рассматривается следующий слу-
чай:
D_____E
\ /
\ /
----->----->
A B C
Кратчайший путь -- ABC, второй -- ABDEBC.
Для того, чтобы его обработать, достаточно найти кратчайший
нетривиальный путь из каждой вершины в нее же. Для этого в алго-
ритме Дейкстры достаточно на нулевом шаге не выставлять пометку
"Просмотрено" на начальной вершине.