| Условие задачи | | Прогресс |
|
Темы:
Способы задания графа
Неориентированный граф задан матрицей смежности. Найдите степени всех вершин графа.
Формат входных данных
В первой строке вводится число n (1 ≤ n ≤ 100) – количество вершин в графе. Далее идет n строк по n чисел, каждое из которых равно 0 или 1, – его матрица смежности.
Формат выходных данных
Выведите n чисел – степени вершин графа (по одному числу в строке).
| |
![]()
|
|
Темы:
Способы задания графа
Простые задачи на перебор
Штирлиц ехал на машине, увидел голосующего Бормана, и проехал мимо. Через некоторое время он снова увидел голосующего Бормана, и снова проехал мимо. Вскоре он опять увидел голосующего Бормана.
- Издевается! - подумал Борман.
- Кольцевая! - догадался Штирлиц.
В городе N площадей. Любые две площади соединены между собой ровно одной дорогой с двусторонним движением. В этом городе живет Штирлиц. У Штирлица есть хобби - он любит воскресным утром выйти из дома, сесть в машину, выбрать какой-нибудь кольцевой маршрут, проходящий ровно по трем площадям (то есть сначала он едет с какой-то площади на какую-то другую, потом - на третью, затем возвращается на начальную, и опять едет по этому маршруту). Он воображает, что где-то на этом пути стоит Борман. И так вот ездит Штирлиц все воскресенье, пока голова не закружится, и радуется...
Естественно, что Штирлицу хочется проезжать мимо точки, в которой, как он воображает, стоит Борман, как можно чаще. Для этого, естественно, выбранный Штирлицем маршрут должен быть как можно короче. Напишите программу, которая выберет оптимальный для Штирлица маршрут.
Входные данные
В первой строке задается число N (3 <= N <= 100). В последующих строках содержится матрица NxN расстояний между площадями (число в позиции i,j обозначает длину дороги, соединяющей i-ую и j-ую площади). Все числа в матрице (кроме стоящих на главной диагонали) - натуральные, не превышающие 1000. Матрица симметрична относительно главной диагонали, на главной диагонали стоят 0.
Выходные данные
Требуется вывести три числа — номера площадей в оптимальном маршруте. Если маршрутов несколько, выведите любой из них.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
5
0 1 9 9 2
1 0 9 9 9
9 9 0 9 9
9 9 9 0 9
2 9 9 9 0 |
1 2 5 |
| |
![]()
|
|
Темы:
Способы задания графа
Дед Мороз составляет схему дорог, по которой можно будет кратчайшим образом посетить N городов. Для простоты он пронумеровал все города номерами 1,..., N. Города соединены M количеством дорог. I-я дорога (1<=i<=M) соединяет город Ai и город Bi. Прежде чем построить оптимальный маршрут Дед Мороз хочет знать с какими городами связан каждый город. Помогите Деду Морозу.
Выведите N строк следующим образом.
- Пусть
di - количество городов, непосредственно связанных с городом i (1<=i<=N), и этими городами будут города ai,1, ..., ai,di,перечисленных в порядке возрастания.
I-я строка (1<=i<=N) должна содержать di+1 целое число: di, ai,1,...,ai,di в указанном порядке, разделенные пробелами.
Входные данные
Первая строка входных данных содержит два целых числа, разделенных одним пробелом N и M (2 <= N <= 105, 1 <= M <= 105). Далее следует M строк, каждая из которых содержит 2 числа Ai и Bi (1 <= Ai < Bi <= N, 1 <= i <= M).
Если i≠j, то (Ai, Bi)≠(Aj, Bj). Все числа целые.
Выходные данные
Выведите N строк по формату, описанному в условии задачи.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
6 6
3 6
1 3
5 6
2 5
1 2
1 6 |
3 2 3 6
2 1 5
2 1 6
0
2 2 6
3 1 3 5 |
| 2 |
5 10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5 |
4 2 3 4 5
4 1 3 4 5
4 1 2 4 5
4 1 2 3 5
4 1 2 3 4 |
| |
![]()
|
|
Темы:
Кратчайшие пути в графе
Обход в ширину
Способы задания графа
Миша путешествует по стране на автомобиле. В стране есть несколько городов, соединенных дорогами, на каждой дороге может быть некоторое число ям.
Мише очень нравится ездить по дорогам на которых много ям, - он участвует в популярном телешоу "Неперсистентные машинки" и за каждую посещенную яму ему платят по одной монете.
Он начинает путь в любом из городов страны и затем путешествует по дорогам между городами. По каждой дороге Миша может проехать сколько угодно раз но ему платят за посещение любой ямы только один раз.
Помогите Мише найти самый выгодный маршрут.
Формат входных данных
В первой строке содержатся два целых числа n и m количество городов и дорог соединяющих города в стране соответственно (1 <= n <= 105 , 0<= m <= 105)
В следующих m строках содержится по три целых числа, разделенных пробелами номера, - городов, соединенных очередной дорогой и количество ям на этой дороге соответственно. Количество ям на каждой дороге неотрицательное число не превосходящее 106.
Гарантируется, что никакая дорога не соединяет город с самим собой и что нет двух дорог соединяющих одинаковые пары городов. Вершины нумеруются с единицы.
Формат выходных данных
Выведите одно число максимальное количество монет которое Миша сможет получить.
| Ввод |
Вывод |
4 4
1 2 1
2 3 1
1 4 1
4 3 0 |
3 |
4 2
1 3 5
2 4 4 |
5 |
Замечание
Все дороги двусторонние; проехав в любую сторону по дороге, Миша посещает все ямы на этой дороге. Обратите внимание, что между некоторыми парами городов может не существовать пути по имеющимся дорогам.
| |
![]()
|
|
Темы:
Способы задания графа
Ориентированный граф задан матрицей смежности, выведите его представление в виде списка ребер.
Формат входных данных
На вход программы поступает число n (1 ≤ n ≤ 100) – количество вершин графа, а затем n строк по n чисел, каждое из которых равно 0 или 1, – его матрица смежности.
Формат выходных данных
Выведите список ребер заданного графа в порядке возрастания номеров вершин.
| |
![]()
|
|
Темы:
Способы задания графа
Простой ориентированный граф задан списком ребер, выведите его представление в виде матрицы смежности.
Формат входных данных
На вход программы поступают числа n ( 1 ≤ n ≤ 100) - количество вершин в графе и m (1 ≤ m ≤ n(n-1)) – количество ребер. Затем следует m пар чисел – ребра графа.
Формат выходных данных
Выведите матрицу смежности заданного графа.
| |
![]()
|
|
Темы:
Алгоритмы на графах
Способы задания графа
Простой неориентированный граф задан списком ребер, выведите его представление в виде матрицы смежности.
Формат входных данных
В первой строке задаются числа n (\(1<=n<=100\)) – количество вершин в графе и m (\(1<=m<=n(n - 1)/2\)) – количество ребер. Далее следует m пар чисел – ребра графа (каждая пара чисел в отдельной строке).
Формат выходных данных
Выведите матрицу смежности заданного графа.
| |
![]()
|
Темы:
Алгоритмы на графах
Способы задания графа
Простой неориентированный граф задан матрицей смежности, выведите его представление в виде списка ребер.
Формат входных данных
Входные данные включают число n (\( 1<=n<=100\)) – количество вершин в графе, а затем n строк по n чисел, каждое из которых равно 0 или 1, – его матрицу смежности.
Формат выходных данных
Выведите список ребер заданного графа (в любом порядке).
| |
![]()
|
|
Темы:
Алгоритмы на графах
Способы задания графа
По заданной матрице смежности неориентированного графа определите, содержит ли он петли.
Формат входных данных
В первой строке задается число n (\(1<=n<=100\)) – количество вершин графа. Затем задается матрица смежности - n строк по n чисел, каждое из которых равно 0 или 1.
Формат выходных данных
Выведите «YES», если граф содержит петли, и «NO» в противном случае.
| |
![]()
|
|
Темы:
Алгоритмы на графах
Способы задания графа
По заданной квадратной матрице n×n из нулей и единиц определите, может ли данная матрица быть матрицей смежности простого неориентированного графа.
Формат входных данных
В первой строке задается число n (\(1<=n<=100\)) – размер матрицы. Затем задается сама матрица - n строк по n чисел, каждое из которых равно 0 или 1.
Формат выходных данных
Выведите «YES», если приведенная матрица может быть матрицей смежности простого неориентированного графа, и «NO» в противном случае
| |
![]()
|
|
Темы:
Алгоритмы на графах
Способы задания графа
В галактике "Milky Way" на планете "Neptune" есть N городов, некоторые из которых соединены дорогами. Император "Maximus" галактики "Milky Way" решил провести инвентаризацию дорог на планете "Neptune". Но, как оказалось, он не силен в математике, поэтому он просит вас сосчитать количество дорог.
Формат входных данных
В первой строке задается число N (\(0<=N<=100\)). В следующих N строках записано по N чисел, каждое из которых является единичкой или ноликом. Причем, если в позиции (i,j) квадратной матрицы стоит единичка, то i-ый и j-ый города соединены дорогами, а если нолик, то не соединены.
Формат выходных данных
Вывести одно число - количество дорог на планете "Neptune".
Примечание
Все дороги двусторонние, то есть если есть дорога из города i в город j, то есть и дорога из города j в город i, и это та же самая дорога.
| |
![]()
|
|
Темы:
Алгоритмы на графах
Способы задания графа
В подземелье M тоннелей и N перекрестков, каждый тоннель соединяет какие-то два перекрестка. Мышиный король решил поставить по светофору в каждом тоннеле перед каждым перекрестком. Напишите программу, которая посчитает, сколько светофоров должно быть установлено на каждом из перекрестков. Перекрестки пронумерованы числами от 1 до N.
Формат входных данных
В первой строке записано два числа N и M (\(0<N<=100\), \(0<=M<=N*(N-1)/2\) ). В следующих M строках записаны по два числа i и j (\(1<=i,j<=N\)), которые означают, что перекрестки i и j соединены тоннелем.
Формат выходных данных
Вывести N чисел: k-ое число означает количество светофоров на k-ом перекрестке.
Примечание
Можно считать, что любые два перекрестка соединены не более, чем одним тоннелем. Нет тоннелей от перекрестка i до него самого.
| |
![]()
|
|
Темы:
Алгоритмы на графах
Способы задания графа
В Банановой республике очень много холмов, соединенных мостами. На химическом заводе произошла авария, в результате чего испарилось экспериментальное удобрение "зован". На следующий день выпал цветной дождь, причем он прошел только над холмами, в некоторых местах падали красные капли, в некоторых - синие, а в остальных - зеленые, в результате чего холмы стали соответствующего цвета. Президенту Банановой республики это понравилось, но ему захотелось покрасить мосты между вершинами холмов так, чтобы мосты были покрашены в цвет холмов, которые они соединяют. К сожалению, если холмы разного цвета, то покрасить мост таким образом не удастся.
Посчитать количество таких "плохих" мостов.
Формат входных данных
В первой строке записано N (\(0<N<=100\)) - число холмов. Далее идет матрица смежности, описывающая наличие мостов между холмами (1-мост есть, 0-нет). В последней строке записано N чисел, обозначающих цвет холмов: 1 - красный; 2 - синий; 3 - зеленый.
Формат выходных данных
Вывести количество "плохих" мостов.
| |
![]()
|
|
Темы:
Способы задания графа
В городе Лост-Хевен произошла серия загадочных преступлений. Жители напуганы и не знают, кому можно доверять. Местный Шериф позвал на помощь знаменитого детектива Нормана, чтобы тот помог ему найти главаря мафии.
Норман принялся за дело и опросил всех жителей города. В итоге он теперь знает, кто кого боится.
Норман знает, что главным подозреваемым будет тот житель города, который удовлетворяет следующим условиям:
1) Подозреваемый никого не боится.
2) Все остальные жители боятся подозреваемого.
3) Существует ровно один такой человек, который удовлетворяет первым двум условиям.
Вы - программист, который помогает Норману. Норман дал вам информацию в виде списка, кто кого боится. Помогите Норману определить главного подозреваемого.
Формат входных данных
В первой строке записано натуральное число N - количество жителей города Лост-Хевен (1 <= N <= 1000). Во второй строке содержится неотрицательное число K (0 <= K <= 104) - количество записей сделанных Норманом после опроса всех жителей города. В следующих K строках записано по два числа (ai, bi) - обозначающие то, что i-й житель a боится жителя b (1 <= ai, bi <= n, ai не равно bi, каждая пара (ai, bi) уникальна).
Формат выходных данных
Выведите номер подозреваемого. Если выявить подозреваемого не представляется возможным, то в ответе укажите число -1.
| |
![]()
|
|
Темы:
Двумерные массивы
Задача на реализацию
Способы задания графа
Обход в ширину
Двумерные массивы
В лаборатории биоинформатики ученые проводят эксперименты по распространению искусственно созданных вирусов. Для эксперимента используется специальная лабораторная установка, представляющая собой таблицу из n × m ячеек. В каждую ячейку помещается живая клетка. Ученые заражают вирусом некоторые клетки, всего исходно заражается не более 8 клеток.
Каждую секунду среди незараженных клеток, имеющих зараженную клетку в соседней по стороне ячейке, ровно одна клетка заражается вирусом.
Ученые заинтересовались, какие конфигурации зараженных клеток могут получиться через t секунд. Для начала они хотят посчитать число таких конфигураций. Помогите им это сделать.
Формат входных данных
В первой строке входного файла находятся целые числа n, m и t (1 ≤ n, m ≤ 100, 1 ≤ t ≤ 6) — размеры таблицы и количество секунд. Каждая из следющих n строк содержит m символов. Символ «.» означает, что в изначальной конфигурации клетка не заражена, а символ «*» — что заражена. Количество «*» в таблице не превышает 8. Гарантируется, что незараженных клеток в исходной конфигурации не меньше t.
Формат выходных данных
Выведите количество различных возможных конфигураций таблицы после t секунд.
| Ввод |
Вывод |
2 2 1
*.
.. |
2 |
2 2 2
*.
.. |
3 |
2 2 3
*.
.. |
1 |
| |
![]()
|