ЛАБОРАТОРНАЯ №4
Алгоритмы на графах
A. Длина пути (поиск в ширину)
В неориентированном графе требуется найти длину минимального пути между двумя вершинами. Гарантируется, что путь существует.
Входные данные
Во входном файле записаны в первой строке число N - количество вершин в графе (1<N≤100) и M – количество ребер. Затем записаны M пар целых чисел – номера вершин определяющих ребра. Затем записаны номера двух вершин - начальной и конечной.
Выходные данные
В выходной файл выведите в первой строке - длину пути (количество ребер, которые нужно пройти), а во второй путь от начальной до конечной вершины.
Пример
| input.txt | output.txt |
| 7 6 1 2 1 5 3 4 2 3 3 6 6 7 3 5 | 3 2 1 5 |
B. Все цепи
Имеется n городов пронумерованных с 1 до n и m соединяющих дорог. Найти всевозможные маршруты автобусов с города с номером start.
В терминах теории графов: дан неориентированный граф с n вершинами и c m ребрами. Напечатать все цепи с данной вершины start.
| input.txt | output.txt |
| 4 6 1 2 1 3 1 5 2 3 3 4 4 5 | 1 2 3 4 5 1 2 3 4 1 2 3 1 2 1 3 2 1 3 4 5 1 3 4 1 3 1 5 4 3 2 1 5 4 3 1 5 4 1 5 |
C. Network
Андрей работает системным администратором и планирует создание новой сети в своей компании. Всего будет N хабов, они будут соединены друг с другом с помощью кабелей.
Поскольку каждый сотрудник компании должен иметь доступ ко всей сети, каждый хаб должен быть достижим от любого другого хаба — возможно, через несколько промежуточных хабов. Требуется сделать такой план сети (соединения хабов), чтобы суммарная длина кабелей была как можно меньше. Есть еще одна проблема — не каждую пару хабов можно непосредственно соединять по причине проблем совместимости и геометрических ограничений здания. Андрей снабдит вас всей необходимой информацией о возможных соединениях хабов.
Вы должны помочь Андрею найти способ соединения хабов, который удовлетворит всем указанным выше условиям.
Ввод:
Первая строка входного файла содержит два целых числа:./V — количество хабов в сети (2≤ N ≤1000) и М — количество возможных соединений хабов (1≤ М ≤15 000). Все хабы пронумерованы от 1 до N. Следующие М строк содержат информацию о возможных соединениях — номера двух хабов, которые могут быть соединены, и длина кабеля, который требуется, чтобы соединить их. Эта длина — натуральное число, не превышающее 106. Существует не более одного способа соединить каждую пару хабов. Хаб не может быть присоединен сам к себе. Всегда существует хотя бы один способ соединить все хабы.
Вывод:
Сначала выведите сумму длин использованных кабелей в вашем плане. Затем выведите свой план: сначала выведите Р — количество кабелей, которые вы использовали, затем выведите Р пар целых чисел — номера хабов, непосредственно соединенных в вашем плане кабелями.
Пример:
| input.txt | output.txt |
| 4 6 1 2 1 1 3 1 1 4 2 2 3 1 3 4 1 2 4 1 | 1 2 1 3 3 4 |
D. Кратчайший путь
Дан неориентированный граф. Для него вам необходимо найти кратчайшее расстояние от одной заданной вершины до другой.
Входные данные
В первой строке входного файла три числа: N, M, S и F (1≤N≤100; 1≤ S, F≤N), где N - количество вершин графа, M – количество ребер, S - начальная вершина, а F - конечная. В следующих M строках заданы по 3 числа, номера вершин и расстояние между ними.
Выходные данные
В первой строке вывести искомое расстояние или -1, если пути между указанными вершинами не существует. Во второй строке маршрут.
Пример
| Input.txt | Output.txt |
| 4 4 1 4 1 2 6 1 3 2 2 3 3 2 4 5 | 1 3 2 4 |
Индивидуальные задания
1. Кратчайший путь. Даны N городов и связи между ними в виде матрицы смежности. Требуется найти минимальное количество пересадок между двумя городами.
Входные данные
Во входном файле записано сначала число N - количество городов (1≤N≤100). Затем записана матрица смежности (0 обозначает отсутствие связи, 1 - наличие связи). Затем записаны номера городов - начальной и конечной.
Выходные данные
В выходной файл выведите одно число - количество пересадок. Если пути нет – вывести -1.
Пример
| input.txt | output.txt |
| 0 1 0 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 3 5 |
Компоненты связности
В неориентированном графе посчитать количество компонент связности. В графе нет петель и кратных ребер.
Формат входного файла
Во входном файле записаны сначала два числа N и M, задающие соответственно количество вершин и количество ребер (1≤N≤100, 0≤M≤10000), а затем перечисляются ребра. Каждое ребро задается номерами вершин, которые оно соединяет.
Формат выходного файла
В выходной файл выведите одно число – количество компонент
связности.
Примеры
| input.txt | output.txt |
| 3 3 1 2 1 3 2 3 | |
| 5 3 1 2 2 3 2 4 | |
| 5 0 |
3. Минимальный путь. В доме N комнат. Связи между комнатами заданы в виде матрицы смежности. Николай находится в комнате с номером S, Виктор – в комнате P. Сколько комнат посетит Коля, чтобы найти Виктора (включая комнату Виктора). Гарантируется, что путь существует.
Входные данные
Во входном файле записано сначала число N - количество комнат (1≤N≤100). Затем записана матрица смежности (0 обозначает отсутствие связи, 1 - наличие связи). Затем записаны номера комнат - Николая и Виктора.
Выходные данные
В выходной файл выведите одно число - количество посещенных комнат.
Пример
| input.txt | output.txt |
| 0 1 0 1 0 1 0 1 0 0 0 1 0 1 0 1 0 1 0 0 0 0 0 1 0 1 5 |
Длинный путь
Имеется n городов пронумерованных с 1 до n и m соединяющих дорог. Расстояния между любыми двумя городами равны 1. Найти длину пути между двумя самыми удаленными городами.
| input.txt | output.txt |
| 5 5 1 2 1 3 2 3 3 4 4 5 |
Расстояние
Имеется n городов пронумерованных с 1 до n и m соединяющих дорог. Найти три города, сумма расстояний между которыми минимальна..
Входные данные
В первой строке заданы два целых числа N и M – количество городов и количество дорог. Со второй строки заданы номера городов соединенных дорогами и их длины.
Выходные данные
Напечатать номера найденных городов в порядке возрастания их номеров и суммарную длину.
Пример
| input.txt | output.txt |
| 5 5 1 2 8 1 3 4 2 3 7 3 4 8 4 5 3 | 3 4 5 |
Поиск.
В доме N комнат. Петя находится в комнате с номером S, Алеша – в комнате P. Сколько комнат посетит Петя, чтобы найти Алешу (включая комнату Алеши). Гарантируется, что путь существует.
Входные данные
Во входном файле записаны сначала числа N и M - количество комнат и количество путей сообщения между комнатами(1≤N≤100). В следующих строках заданы ребра. Затем записаны номера комнат - Пети и Алеши.
Выходные данные
В выходной файл выведите одно число - количество посещенных комнат.
Пример
| input.txt | output.txt |
| 5 5 1 5 2 5 2 4 3 4 4 5 1 3 |
Охотники
На охоту поехали n человек. Половина из них не имели патронов. Охотники разделились на два равные группы: первая группа с патронами, вторая – без патронов. Первая группа решила курировать над второй группой, т.е. выдавать патроны второй группе. Члены первой группы, пронумерованные от 1 до n div 2, указали номера членов второй группы, с которыми они могут ходить в паре.
Определите количество пар, которое может образоваться, и укажите эти пары.
Формат входных данных
В первой строке входного файла заданы два целых числа n – количество охотников и m –количество охотников, которым изъявили желание помочь. Со второй строки m пар чисел, первое число – номер охотника первой группы, второе число номер охотника второй группы которому первый готов помочь.
Формат выходных данных
В первой строке максимальное количество пар, которое может образоваться, со второй строки, номера образовавшихся пар.
Пример
| input.txt | output.txt |
| 10 5 2 6 2 7 3 9 4 8 5 7 | 2 6 5 7 4 8 3 9 |
Изолированные города
В государстве N городов с номерами 1.2….N. Некоторые города связаны между собой дорогами и образуют штат. Сколько штатов в государстве.
Формат входного файла
Во входном файле записаны сначала два числа N и M, задающие соответственно количество городов и количество дорог (1≤N≤100, 0≤M≤1000), а затем перечисляются попарно связанные дорогами города. Каждая дорога задается номерами городов, которые она соединяет.
Формат выходного файла
В выходной файл выведите одно число – количество штатов в государстве.
Примеры
| input.txt | output.txt |
| 6 3 1 3 1 5 2 6 | |
| 7 0 |
Все дороги
Имеется n городов пронумерованных с 1 до n и m соединяющих дорог. Найти количество всевозможных маршрутов с города с номером start до города с номером finish. Маршруты без циклов.
Формат входного файла
Во входном файле в первой строке записаны два числа n и m, задающие соответственно количество городов и количество дорог (1≤n≤100, 0≤m≤10000), со второй строки заданы m пар чисел - дороги. В последней строке заданы два числа - start и finish.
Формат выходного файла
В выходной файл выведите одно число – количество групп озер.
Примеры
| input.txt | output.txt | Примечание |
| 4 6 1 2 1 3 1 5 2 3 3 4 4 5 1 3 | Имеем следующие пути: 1 2 3 1 3 5 4 3 |
Линия электропередач
Администрация улуса планирует проведение новой линии электропередач. В улусе всего N поселков. Требуется сделать такой план сети электропередач, чтобы общая длина проводов была минимальна.
Ввод:
Первая строка входного файла содержит два целых числа:./V — количество поселков в улусе (2≤ N ≤100) и М — количество возможных соединений поселков (1≤ М ≤1500). Все улусы пронумерованы от 1 до N. Следующие М строк содержат информацию о возможных соединениях — номера двух поселков, которые могут быть соединены, и длина провода, которая требуется, чтобы соединить их. Эта длина — натуральное число.
Вывод:
Вывести одно число – общая длина провода.
Пример:
| input.txt | output.txt |
| 5 7 1 2 4 1 3 1 1 4 2 1 5 1 2 3 2 3 5 5 4 5 3 |
Два города
Имеется n городов пронумерованных с 1 до n и m соединяющих их дорог. Расстояния между любыми двумя городами равны 1. Которая из двух городов A и B наиболее удалена от города с номером 1. Если они на одинаковом расстоянии, напечатать любой из них.
Формат входного файла
В первой строке заданы n и m, со второй строки пары целых чисел – номера вершин образующих ребро. В последней строке заданы вершины A и B.
Формат выходного файла
Вывести одно число – номер вершины (A или B) наиболее удаленного от города номер 1.
Пример
| input.txt | output.txt |
| 5 5 1 5 2 5 2 4 3 4 4 5 3 5 |
Два не связанных города
В республике N городов пронумерованных с 1 до N. M городов связаны дорогами. Найти два города не связанных дорогами.
Формат входного файла
Во входном файле записаны сначала два числа N и M, задающие соответственно количество вершин и количество ребер (1≤N≤100, 1≤M≤10000), а затем перечисляются ребра. Каждое ребро задается номерами вершин, которые оно соединяет.
Формат выходного файла
В выходной файл выведите два числа – не связанные между собой города. Если их несколько, то напечатать любой из них. Гарантируется, что такие два города есть.
связности.
Пример
| input.txt | output.txt |
| 6 4 1 2 2 3 2 4 5 6 | 1 5 |
Три города
В республике N городов пронумерованных с 1 до N. M городов связаны дорогами. Найти три города не связанных между собой дорогами.
Формат входного файла
Во входном файле записаны сначала два числа N и M, задающие соответственно количество вершин и количество ребер (1≤N≤100, 1≤M≤10000), а затем перечисляются ребра. Каждое ребро задается номерами вершин, которые оно соединяет.
Формат выходного файла
В выходной файл выведите два числа – не связанные между собой города. Если их несколько, то напечатать любой из них. Гарантируется, что такие города есть.
связности.
Пример
| input.txt | output.txt |
| 7 4 1 2 2 3 2 4 5 6 | 4 5 7 |
14. Домино
Набор домино состоит из прямоугольных костяшек, каждая из которых разделена на две половинки линией, параллельной более короткой стороне. На каждой из половинок нарисованы точки, количество которых соответствует числу от 0 до M включительно. На костяшках полного набора домино обозначены все возможные различные пары чисел, например, если M равно 3, то полный набор содержит 10 костяшек: (0, 0), (0, 1), (0, 2), (0, 3), (1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3).
Из костяшек можно выкладывать цепочки, соединяя пары костяшек короткими сторонами, если количества точек на соседних с местом соединения половинках костяшек равны.
Некоторые костяшки были удалены из полного набора. Требуется определить, какое минимальное количество цепочек нужно выложить из оставшихся в наборе костяшек, чтобы каждая из них принадлежала ровно одной цепочке.
Задание
Напишите программу, которая по информации о наборе домино должна ответить, какое минимальное количество цепочек нужно выложить.
Входные данные
В первой строке входного файла содержится одно целое число M (0≤M≤100), которое соответствует максимально возможному количеству точек на половинке костяшки. Во второй строке записано одно целое число N, равное количеству костяшек, удаленных из полного набора. Каждая і -я из последующих N строк содержит по два числа Ai и Bі. Это количества точек на половинках i -й удалённой костяшки.
Выходные данные
Единственная строка выходного файла должна содержать одно целое число L – минимальное количество цепочек.
Пример
| INPUT.TXT | OUTPUT.TXT |
| 7 5 2 4 |
Соседние города
В некотором государстве n городов. Найти два ближайших города от заданного города A.
Входные данные
В первой строке входного файла три числа: N, M, A (3≤N≤100), где N - количество вершин графа, M – количество ребер, A - начальная вершина. В следующих M строках заданы по 3 числа, номера вершин и расстояние между ними.
Выходные данные
Номера двух ближайших городов. Если их несколько, напечатать любые из них.
Пример
| Input.txt | Output.txt |
| 4 4 2 1 2 6 1 3 2 2 3 3 2 4 5 | 3 4 |
Удаленные города
Имеется n городов пронумерованных с 1 до n и m соединяющих дорог. Расстояния между любыми двумя городами равны 2. Найти длину пути между двумя самыми удаленными городами.
| input.txt | output.txt |
| 6 7 1 2 1 3 3 5 2 3 3 4 4 5 4 6 |
Новые требования
В ИМИ СВФУ N студентов и N компьютеров. В институте вводятся новые требования к секретности. В соответствии с этими требованиями, для каждого студента будут определены ровно К компьютеров, к которым этот студент будет иметь допуск (т. е. за которыми этот студент будет иметь право работать), причём так, что к каждому компьютеру будут иметь допуск ровно К студент.
Информация о том, какой студент к какому компьютеру будет иметь допуск, будет известна лишь непосредственно перед вступлением новых требований в силу. Таким образом, чтобы не прерывать работу компьютерных классов, студенты должны будут быстро решить, кто за каким компьютером будет работать. Для этого им необходимо заранее написать программу, которая по любому распределению допусков студентов найдёт рассадку студентов по компьютерам, удовлетворяющую этим допускам.
Из общих соображений секретности известно лишь, что К будет равняться или 1, или 2, или 4; поэтому ваша программа должна уметь работать для любого из этих трех значений К.
Формат входных данных
В первой строке входного файла записаны натуральные числа N и К (1≤ N ≤ 500). Далее следуют K × N строк, в каждой из которых записаны два натуральных числа — номер студента и номер компьютера, к которому этот студент имеет допуск.
Гарантируется, что каждый студент имеет допуск ровно к К компьютерам, что к каждому компьютеру ровно К студентов имеют допуск, и что K равно либо 1, либо 2, либо 4.
Формат выходных данных
В выходной файл выведите N строк, в каждой по два числа — номер студента и номер компьютера, за которым он должен работать. Строки можно выводить в произвольном порядке.
Если есть несколько решений, выведите любое. Можно доказать, что для любого входного файла, удовлетворяющего указанным ограничениям, всегда имеется как минимум одно решение.
Примеры
| input.txt | output.txt |
| 3 1 2 3 3 1 1 2 | 3 1 1 2 2 3 |
| 2 2 1 2 2 1 2 2 1 1 | 1 2 2 1 |
Три города
В некотором государстве n городов. Найти два города удаленных от города A на одинаковом расстоянии. Гарантируется, что такие города есть.
Входные данные
В первой строке входного файла три числа: N, M, A (3≤N≤100), где N - количество вершин графа, M – количество ребер, A - начальная вершина. В следующих M строках заданы по 3 числа, номера вершин и расстояние между ними.
Выходные данные
Номера двух городов равноудаленных от города A. Если их несколько, напечатать любые из них.
Пример
| Input.txt | Output.txt |
| 6 6 2 1 2 6 1 3 2 2 3 4 2 4 5 4 6 1 3 5 2 | 5 6 |
19. Домино - 2
Набор домино состоит из прямоугольных костяшек, каждая из которых разделена на две половинки линией, параллельной более короткой стороне. На костяшках полного набора домино обозначены все возможные различные пары чисел: (0, 0), (0, 1), (0, 2),…,(0, 6), (1, 1), (1, 2), (1, 3),…,(1, 6), (2, 2),…, (2, 6), (3,3), (3,4),…,(3,6), …, (6,6).
Из костяшек можно выкладывать цепочки, соединяя пары костяшек короткими сторонами, если количества точек на соседних с местом соединения половинках костяшек равны.
Некоторые костяшки были удалены из полного набора. Требуется определить, самую длинную цепочку в заданном наборе, которую можно построить.
Входные данные
В первой строке записано одно целое число N, равное количеству костяшек в наборе. Каждая і -я из последующих N строк содержит по два числа Ai и Bі. Это количества точек на половинках i -й костяшки.
Выходные данные
В первой строке вывести длину цепочки.
Пример
| INPUT.TXT | OUTPUT.TXT |
| 6 5 5 4 4 3 3 2 1 1 5 2 |
Система дорог
Даны N городов соединенных M дорогами. С любого города можно добраться до любого другого города. Из них оставить дороги, чтобы не осталось циклов и сумма длин оставшихся дорог была минимальна.
Входные данные
В первой строке заданы два целых числа N и M – количество городов и количество дорог. Со второй строки заданы номера городов соединенных дорогами и их длины.
Выходные данные
Напечатать одно число – суммарная длина
Пример
| INPUT.TXT | OUTPUT.TXT |
| 5 7 1 2 1 1 3 3 1 4 2 2 3 1 3 4 1 4 5 1 3 5 4 |
Ближайшие города
Имеется n городов пронумерованных с 1 до n и m соединяющих их дорог. Расстояния между любыми двумя городами равны 1. Найти два города A и B наименее удаленные от города с номером start. Если их несколько напечатать любые два из них.
Формат входного файла
В первой строке заданы n и m, со второй строки пары целых чисел – номера вершин образующих ребро. В последней строке заданы вершины start.
Формат выходного файла
Вывести два числа – номера вершин A и B ближайшие к городу номер start.
Пример
| input.txt | output.txt |
| 5 5 1 3 2 3 2 4 4 5 4 3 | 3 4 |
Поиск
В тайге N озер. Некоторые озера связаны дорогами. Связанные между собой озера образуют группы. Посчитать количество групп озер.
Формат входного файла
Во входном файле записаны сначала два числа N и M, задающие соответственно количество озер и количество дорог (1≤N≤100, 0≤M≤10000), а затем перечисляются дороги. Каждая дорога задается номерами озер, которые она соединяет.
Формат выходного файла
В выходной файл выведите одно число – количество групп озер.
Примеры
| input.txt | output.txt |
| 3 3 1 2 1 3 2 3 | |
| 5 3 1 2 2 3 5 4 | |
| 7 0 |
23. Пустой
24. Поиск. В доме N комнат. Петя находится в комнате с номером S, Алеша – в комнате P. Сколько комнат посетит Петя, чтобы найти Алеша (включая комнату Алеши). Гарантируется, что путь существует.
Входные данные
Во входном файле записаны сначала числа N и M - количество комнат и количество путей сообщения между комнатами(1≤N≤100). В следующих строках заданы ребра. Затем записаны номера комнат - Пети и Алеши.
Выходные данные
В выходной файл выведите одно число - количество посещенных комнат.
Пример
| input.txt | output.txt |
| 5 5 1 5 2 5 2 4 3 4 4 5 1 3 |
Расстояние между двумя ближайшими
В некотором государстве n городов. Найти расстояние между двумя ближайшими городами от города A.
Входные данные
В первой строке входного файла три числа: N, M, A (3≤N≤100), где N - количество вершин графа, M – количество ребер, A - начальная вершина. В следующих M строках заданы по 3 числа, номера вершин и расстояние между ними.
Выходные данные
Расстояние между двумя ближайшими городами от города A. Гарантируется, что решение единственно.
Пример
| Input.txt | Output.txt |
| 4 4 2 1 2 6 1 3 2 2 3 3 2 4 5 |
Все дороги
Имеется n городов пронумерованных с 1 до n и m соединяющих дорог. Найти количество всевозможных маршрутов с города с номером start до города с номером finish. Маршруты без циклов.
Формат входного файла
Во входном файле в первой строке записаны два числа n и m, задающие соответственно количество городов и количество дорог (1≤n≤100, 0≤m≤10000), со второй строки заданы m пар чисел - дороги. В последней строке заданы два числа - start и finish.
Формат выходного файла
В выходной файл выведите одно число – количество групп озер.
Примеры
| input.txt | output.txt | Примечание |
| 4 6 1 2 1 3 1 5 2 3 3 4 4 5 1 3 | Имеем следующие пути: 1 2 3 1 3 5 4 3 |
Удаленные города
Имеется n городов пронумерованных с 1 до n и m соединяющих дорог. Расстояния между любыми двумя городами равны 2. Найти длину пути между двумя самыми удаленными городами.
| input.txt | output.txt |
| 6 7 1 2 1 3 3 5 2 3 3 4 4 5 4 6 |
Три города
В некотором государстве n городов. Найти три города удаленных от города A на одинаковом расстоянии. Гарантируется, что такие города есть.
Входные данные
В первой строке входного файла три числа: N, M, A (3≤N≤100), где N - количество вершин графа, M – количество ребер, A - начальная вершина. В следующих M строках заданы по 3 числа, номера вершин и расстояние между ними.
Выходные данные
Номера трех ближайших городов. Если их несколько, напечатать любые из них.
Пример
| Input.txt | Output.txt |
| 6 6 2 1 2 6 1 3 2 2 3 4 2 4 5 4 6 1 3 5 2 | 1 5 6 |
Расстояние
Имеется n городов пронумерованных с 1 до n и m соединяющих дорог. Найти три города, сумма расстояний между крайними городами минимальна.
Входные данные
В первой строке заданы два целых числа N и M – количество городов и количество дорог. Со второй строки заданы номера городов соединенных дорогами и их длины.
Выходные данные
Напечатать номера найденных городов, суммарную длину и путь.
Пример
| input.txt | output.txt |
| 5 5 1 2 8 1 3 4 2 3 7 3 4 8 4 5 3 | 3 4 5 |
Путь в ближайший
Имеется n городов пронумерованных с 1 до n и m соединяющих дорог. Найти длину пути и путь между двумя самыми ближайшими, не соседними городами.
Входные данные
В первой строке заданы два целых числа N и M – количество городов и количество дорог. Со второй строки заданы номера городов соединенных дорогами и их длины.
Выходные данные
Напечатать номера найденных городов, суммарную длину и путь. Номера вершин напечатать в возрастающем порядке.
Пример
| input.txt | output.txt |
| 5 5 1 2 8 1 3 4 2 3 7 3 4 8 4 5 3 | 3 5 3 4 5 |