| Условие задачи | | Прогресс |
|
Темы:
Алгоритмы на графах
Напишите программу, которая считает количество дорог в городе Новые Васюки. Схема дорог задана как матрица смежности графа. На некоторых дорогах введено одностороннее движение.
Входные данные
В первой строке вводится количество перекрёстков в Новых Васюках N ( 1 ≤ N ≤ 1000 ). В следующих N строках записано по N чисел, разделённых пробелами – элементы матрицы смежности графа, который описывает схему дорог.
Выходные данные
Программа должна вывести одно число – количество дорог в Новых Васюках. Дороги с двусторонним движением нужно считать только один раз.
|
Ввод |
Вывод |
|
5
0 1 1 1 0
1 0 1 0 1
1 1 0 1 0
0 0 0 0 0
0 1 0 1 0
|
7 |
| |
![]()
|
|
Темы:
Алгоритмы на графах
Найдите суммарную длину всех дорог в городе Новые Васюки. Схема дорог задана в виде весовой матрицы графа. На некоторых дорогах введено одностороннее движение. Если длины дорог из пункта А в пункт Б разные, это означает, что есть две разные дороги.
Входные данные
В первой строке вводится количество перекрёстков в Новых Васюках N ( 1 ≤ N ≤ 1000 ). В следующих N строках записано по N чисел, разделённых пробелами – длины дорог между каждой парой перекрёстков. Ноль означает, что дороги между этими перекрёстками нет.
Выходные данные
Программа должна вывести одно число – суммарную длину дорог. Дороги с двусторонним движением нужно считать только один раз.
|
Ввод |
Вывод |
|
5
0 2 3 4 0
2 0 5 0 7
3 6 0 8 0
0 0 0 0 0
0 7 0 9 0
|
44 |
| |
![]()
|
|
Темы:
Алгоритмы на графах
В галактике "Milky Way" на планете "Neptune" есть N городов, некоторые из которых соединены дорогами. Император "Maximus" галактики "Milky Way" решил провести инвентаризацию дорог на планете "Neptune". Но, как оказалось, он не силен в математике, поэтому он просит вас сосчитать количество дорог.
Входные данные
В первой строке задается число N (\(0<=N<=100\)). В следующих N строках записано по N чисел, каждое из которых является единичкой или ноликом. Причем, если в позиции (i,j) квадратной матрицы стоит единичка, то i-ый и j-ый города соединены дорогами, а если нолик, то не соединены.
Выходные данные
Вывести одно число - количество дорог на планете "Neptune".
Примечание
Все дороги двусторонние, то есть если есть дорога из города i в город j, то есть и дорога из города j в город i, и это та же самая дорога.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
5
0 1 0 0 0
1 0 1 1 0
0 1 0 0 0
0 1 0 0 0
0 0 0 0 0
|
3 |
| |
![]()
|
|
Темы:
Алгоритмы на графах
В подземелье 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 до него самого.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
7 10
5 1
3 2
7 1
5 2
7 4
6 5
6 4
7 5
2 1
5 3
|
3 3 2 2 5 2 3 |
| |
![]()
|
|
Темы:
Алгоритмы на графах
В Банановой республике очень много холмов, соединенных мостами. На химическом заводе произошла авария, в результате чего испарилось экспериментальное удобрение "зован". На следующий день выпал цветной дождь, причем он прошел только над холмами, в некоторых местах падали красные капли, в некоторых - синие, а в остальных - зеленые, в результате чего холмы стали соответствующего цвета. Президенту Банановой республики это понравилось, но ему захотелось покрасить мосты между вершинами холмов так, чтобы мосты были покрашены в цвет холмов, которые они соединяют. К сожалению, если холмы разного цвета, то покрасить мост таким образом не удастся.
Посчитать количество таких "плохих" мостов.
Входные данные:
- в первой строке записано N (\(0<N<=100\)) - число холмов;
- далее идет матрица смежности, описывающая наличие мостов между холмами (1-мост есть, 0-нет);
- в последней строке записано N чисел, обозначающих цвет холмов: 1 - красный; 2 - синий; 3 - зеленый.
Выходные данные: вывести количество "плохих" мостов.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
7
0 1 0 0 0 1 1
1 0 1 0 0 0 0
0 1 0 0 1 1 0
0 0 0 0 0 0 0
0 0 1 0 0 1 0
1 0 1 0 1 0 0
1 0 0 0 0 0 0
1 1 1 1 1 3 3
|
4 |
| |
![]()
|
|
Темы:
Алгоритмы на графах
По заданной квадратной матрице n×n из нулей и единиц определите, может ли данная матрица быть матрицей смежности простого неориентированного графа.
Входные данные:
- в первой строке задается число n (\(1<=n<=100\)) – размер матрицы;
- затем задается сама матрица - n строк по n чисел, каждое из которых равно 0 или 1.
Выходные данные: выведите «YES», если приведенная матрица может быть матрицей смежности простого неориентированного графа, и «NO» в противном случае.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
5
0 0 1 0 0
0 0 1 0 1
1 1 0 0 0
0 0 0 0 0
0 1 0 0 0
|
YES |
| |
![]()
|
|
Темы:
Алгоритмы на графах
По заданной матрице смежности неориентированного графа определите, содержит ли он петли.
Входные данные:
- в первой строке задается число n (\(1<=n<=100\)) – количество вершин графа;
- затем задается матрица смежности - n строк по n чисел, каждое из которых равно 0 или 1.
Выходные данные: выведите «YES», если граф содержит петли, и «NO» в противном случае.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
5
1 1 1 1 0
1 0 1 1 1
1 1 0 1 1
1 1 1 1 1
0 1 1 1 0
|
YES |
| |
![]()
|
Темы:
Алгоритмы на графах
Простой неориентированный граф задан матрицей смежности, выведите его представление в виде списка ребер.
Входные данные: входные данные включают число n (\( 1<=n<=100\)) – количество вершин в графе, а затем n строк по n чисел, каждое из которых равно 0 или 1, – его матрицу смежности.
Выходные данные: выведите список ребер заданного графа (в любом порядке).
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
5
0 0 1 0 0
0 0 1 0 1
1 1 0 0 0
0 0 0 0 0
0 1 0 0 0
|
1 3
2 3
2 5 |
| |
![]()
|
|
Темы:
Алгоритмы на графах
Простой неориентированный граф задан списком ребер, выведите его представление в виде матрицы смежности.
Входные данные:
- в первой строке задаются числа n (\(1<=n<=100\)) – количество вершин в графе и m (\(1<=m<=n(n - 1)/2\)) – количество ребер;
- далее следует m пар чисел – ребра графа (каждая пара чисел в отдельной строке).
Выходные данные: выведите матрицу смежности заданного графа.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
5 3
1 3
2 3
2 5
|
0 0 1 0 0
0 0 1 0 1
1 1 0 0 0
0 0 0 0 0
0 1 0 0 0
|
| |
![]()
|
|
Темы:
Динамическое программирование
Алгоритмы на графах
Обход в глубину
Динамическое программирование на графах
В тридесятом государстве есть N деревень. Некоторые пары деревень соединены дорогами. В целях экономии, “лишних” дорог нет, т.е. из любой деревни в любую можно добраться по дорогам единственным образом.
Новейшие исследования показали, что тридесятое государство находится в сейсмически опасной зоне. Поэтому глава государства захотел узнать, какой именно ущерб может принести его державе землетрясение. А именно, он хочет узнать, какое минимальное число дорог должно быть разрушено, чтобы образовалась изолированная от остальных группа ровно из P деревень такая, что из любой деревни из этой группы до любой другой деревни из этой группы по-прежнему можно будет добраться по неразрушенным дорогам (группа изолирована от остальных, если никакая неразрушенная дорога не соединяет деревню из этой группы с деревней не из этой группы).
Вы должны написать программу, помогающую ему в этом.
Формат входных данных
Первая строка входного файла содержит два числа: N и P (1 ≤ P ≤ N ≤ 150). Все остальные строки содержат описания дорог, по одному на строке: описание дороги состоит из двух номеров деревень (от 1 до N), которые эта дорога соединяет. Все числа во входном файле разделены пробелами и/или переводами строки.
Формат выходных данных
В выходной файл выведите единственное число — искомое количество дорог.
Примеры
| № |
Входные данные |
Выходные данные |
Пояснение |
| 1 |
3 2
1 2
3 2 |
1 |
|
| 2 |
11 6
1 2
1 3
1 4
1 5
2 6
2 7
2 8
4 9
4 10
4 11 |
2 |
группа деревень (1, 2, 3, 6, 7, 8) окажется изолированной от остальных, если разрушить дороги 1–4 и 1–5. |
| |
![]()
|
|
Темы:
Алгоритмы на графах
Есть N городов. Есть также шоссе K и железные дороги L, проходящие между городами. Каждое i-я шоссе двунаправленно соединяет рi и qi города, а каждая i-я железная дорога двунаправленно соединяет ri и si города. Нет двух шоссе, соединяющих одну и ту же пару городов. Точно так же, никакие две железные дороги не соединяют одну и ту же пару городов. Будем считать, что города A и B соединены шоссе, если до города B можно добраться из города A по некоторому количеству шоссе. Здесь любой город считается соединенным с собой шоссе. Аналогичным образом, мы также определим возможность сообщения железными дорогами. Для каждого города найдите количество городов, соединенных с этим городом как шоссе, так и железными дорогами.
Входные данные
Входные данные поступают в следующем формате:
N K L
p1 q1
...
pK qK
r1 s1
...
rl sL
Ограничения:
\(2<=N<=2\cdot10^5 \\ 1<=K,L<=10^5 \\ 1<=p_i,q_i,r_i,s_i<=N\\ p_i <q_i \\ r_i<s_i \\ Когда\ i \neq j, (p_i,q_i)\neq(p_j,q_j) \\ ?Когда\ i \neq j, (r_i,s_i)\neq(r_j,s_j)\)
Выходные данные
Выведите N целых чисел в одной строке, разделяя каждое число одним пробелом. Каждое i число должно обозначать количество городов, соединенных с i-м городом как шоссе, так и железными дорогами.
Примеры
| № |
Входные данные |
Выходные данные |
Пояснения |
| 1 |
4 3 1
1 2
2 3
3 4
2 3 |
1 2 2 1 |
Все четыре города связаны между собой дорогами.
Железной дорогой соединены только второй и третий города. Таким образом, ответы для городов 1,2,2 и 1 соответственно. |
| 2 |
4 2 2
1 2
2 3
1 4
2 3 |
1 2 2 1 |
|
| 3 |
7 4 4
1 2
2 3
2 5
6 7
3 5
4 5
3 4
6 7 |
1 1 2 1 2 2 2 |
|
| |
![]()
|
|
Темы:
Интерактивные задачи
Мосты
Алгоритмы на графах
– Это что за остановка – Бологое иль Поповка? – А с платформы говорят: – Это город Ленинград.
«Вот какой рассеянный», Самуил Маршак
Пытаясь спастись от мира спортивного программирования, Алина сбежала на вокзал и уехала прочь на ночной электричке. Минуты медленно уплывали в даль, и уставшую девочку клонило в сон. Ей снился город-сказка, где не надо программировать, а можно гулять, мечтать и наслаждаться жизнью. Внезапно дождь из интерактивных задач разрушил эту идиллию.
Проснувшись и открыв окно, Алина задалась вопросом весьма философского свойства: «Где я?». С перрона потерявшейся девочке сообщили, что этот город, не похожий ни на что вокруг, представляет собой неориентированный граф на n вершинах и m ребрах. Сeй невероятный факт, однако, нисколько не удивил Алину. Она давно мечтала побывать в одном таком городе — Петербурге. Его уникальной отличительной особенностью является то, что хотя бы половина его ребер — мосты (определение дано в конце условия). Так как никакие другие города Алине не интересны, она решила ограничиться расспросом находящихся на платформе эрудированных путешественников. Любой из их них может по данной вершине v сообщить любое ещё не названное ребро, исходящее из нее, или же заявить об отсутствии таковых.
Алина неуверена в своих силах, поэтому попросила вас помочь ей определить, попала ли она в Петербург. Так как её поезд скоро продолжит свой путь, задать больше 3n вопросов не получится.
Обратите внимание, что в графе могут присутствовать петли и кратные ребра.
Протокол взаимодействия
В первой строке стандартного потока ввода даны два целых числа n и m (1 ≤ n, m ≤ 100000 ) — число вершин и ребер в графе соответственно.
Для того, чтобы узнать очередное ребро, исходящее из u-й вершины (1 ≤ u ≤ n), нужно вывести « ? u ». После этого ваша программа на вход получит целое число v (−2 ≤ v ≤ −1 или 1 ≤ v ≤ n) — v=a+b−u, если существует ребро ab, которое инцидентно вершине u и ещё не было названо , −1, если такого ребра не существует и −2, если вы превысили допустимое число запросов. В последнем случае ваша программа должна немедленно завершиться, в ином случае жюри не гарантирует корректность полученного вами вердикта.
Вам разрешается задать не более 3n вопросов.
Чтобы сообщить, что ответ найден, требуется вывести « ! Yes » или « ! No », в зависимости от того, является ли загаданный граф Петербургом. В случае положительного ответа выведите \( {m \over 2}\) строк, по два целых числа ui и vi в каждой (1 ≤ ui, vi ≤ n), обозначающих, что ребро (ui, vi) является мостом. Любое ребро в приведенном списке должно встречаться не более одного раза (кратные ребра считаются различными).
Запрос на вывод ответа не входит в ограничение на 3n запросов.
Примечание
В условии в примере взаимодействия вводимые и выводимые данные расположены для удобства восприятия в хронологическом порядке, при реальном взаимодействии никакие «лишние» переводы строк возникать не должны.
Ввод-вывод в примерах демонстрирует пример взаимодействия вашей программы с проверяющей системой.
В первом примере был загадан граф на трех вершинах с ребрами (1, 2) , (2, 3) и (3, 1) .
Во втором примере была загадан граф на четырех вершинах с ребрами (1, 2) , (2, 3) , (3, 4) и (2, 3) .
Ребро, соединяющее вершины u и v, называется мостом, если после его удаления между вершинами u и v не существует пути.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
3 3
2
2
-1
3
-1
-1 |
? 3
? 1
? 2
? 1
? 1
? 3
! No |
| 2 |
4 4
2
3
2
-1
4
-1
-1
-1 |
? 1
? 2
? 3
? 1
? 3
? 3
? 2
? 4
! Yes
1 2
3 4 |
| |
![]()
|
|
Темы:
Алгоритмы на графах
Кратчайшие пути в графе
Дан неориентированный связный взвешенный граф с N вершинами и M ребрами, который не содержит ни петель, ни двойных ребер. I-е (\(1<=i<=M\)) ребро соединяет вершину ai и вершину bi на расстоянии ci. Будем считать, что петля - это ребро, где \(a_i=b_i\) (\(1<=i<=M\)), а двойные ребра - это два ребра, где \((a_i,b_i)=(a_j,b_j) \) или \((a_i,b_i)=(b_j,a_j)\) (\(1<=i<j<=M\)). Связный граф - это граф, в котором есть путь между каждой парой разных вершин. Найдите количество ребер, которые не входят ни в один кратчайший путь между любой парой различных вершин.
Входные данные
В первой строке задаются два целых числа N и M (\(2<=N<=100\), \(N-1<=M<=min(N \cdot (N-1)/2,1000)\)). Далее идет M строк по три целых числа в каждой строке: ai, bi, ci (\(1<=a_i, b_i<=N\), \(1<=c_i<=1000\)). Данный граф не содержит петель и двойных ребер. Данный граф является связанным.
Выходные данные
Выведите количество ребер в графе, которые не входят ни в один кратчайший путь между любой парой различных вершин.
Примеры
| № |
Входные данные |
Выходные данные |
Пояснения |
| 1 |
3 3
1 2 1
1 3 1
2 3 3
|
1
|
В данном графе кратчайшие пути между всеми парами различных вершин следующие:
Кратчайший путь от вершины 1 к вершине 2: вершина 1 → вершина 2, длина пути равна 1.
Кратчайший путь от вершины 1 к вершине 3: вершина 1 → вершина 3, длина пути равна 1.
Кратчайший путь из вершины 2 в вершину 1: вершина 2 → вершина 1, длина пути равна 1.
Кратчайший путь от вершины 2 к вершине 3: вершина 2 → вершина 1 → вершина 3, длина пути равна 2.
Кратчайший путь от вершины 3 до вершины 1: вершина 3 → вершина 1, длина пути равна 1.
Кратчайший путь от вершины 3 к вершине 2: вершина 3 → вершина 1 → вершина 2, длина пути равна 2.
Таким образом, единственное ребро, которое не содержится ни в одном кратчайшем пути, - это ребро длины 3, соединяющее вершину 2 и вершину 3, поэтому на выходе должно быть 1. |
| 2 |
3 2
1 2 1
2 3 1
|
0
|
Каждое ребро содержится в некотором кратчайшем пути между парой различных вершин. |
| |
![]()
|
|
Темы:
Алгоритмы на графах
Кратчайшие пути в графе
Обход в ширину
Вам дано дерево с N вершинами. Здесь дерево - это разновидность графа, а точнее, связный неориентированный граф с N−1 ребром, где N - количество его вершин. I-е ребро (\(1<=i<=N-1\)) соединяет вершины ai и bi и имеет длину ci.
Вам также дано Q запросов и целое число K. Для каждого j-го запроса (\(1<=j<=Q\)) найдите длину кратчайшего пути от вершины xj к вершине yj через вершину K.
Входные данные
В первой строке записано целое число N (\(3<=N<=10^5\)). В следующих N строках записаны вершины ai и bi (\(1<=a_i,b_i<=N\), \(1<=i<=N-1\)) и длина между ними ci (\(1<=c_i<=10^9\), \(1<=i<=N-1\))
Далее идут два числа Q и K (\(1<=Q<=10^5\), \(1<=K<=N\)). В последних Q строках записаны целые числа xj, yj (\(x_j \neq y_j\),\(x_j \neq K\), \(y_j \neq K\) \(1<=j<=Q\), ).
Заданный граф является деревом.
Выходные данные
Выведите ответы на запросы в Q строках. В j-й строке выведите ответ на j-й запрос.
Примеры
| № |
Входные данные |
Выходные данные |
Пояснение |
| 1 |
5
1 2 1
1 3 1
2 4 1
3 5 1
3 1
2 4
2 3
4 5 |
3
2
4 |
Кратчайшие пути для трех запросов следующие:
Запрос 1: Вершина 2 → Вершина 1 → Вершина 2 → Вершина 4: Длина 1 + 1 + 1 = 3
Запрос 2: Вершина 2 → Вершина 1 → Вершина 3: Длина 1 + 1 = 2
Запрос 3: Вершина 4 → Вершина 2 → Вершина 1 → Вершина 3 → Вершина 5: Длина 1 + 1 + 1 + 1 = 4 |
| 2 |
7
1 2 1
1 3 3
1 4 5
1 5 7
1 6 9
1 7 11
3 2
1 3
4 5
6 7 |
5
14
22 |
Путь для каждого запроса должен проходить через вершину K = 2. |
| 3 |
10
1 2 1000000000
2 3 1000000000
3 4 1000000000
4 5 1000000000
5 6 1000000000
6 7 1000000000
7 8 1000000000
8 9 1000000000
9 10 1000000000
1 1
9 10 |
17000000000 |
|
| |
![]()
|
|
Темы:
Алгоритмы на графах
Кратчайшие пути в графе
Давилон - самый крупный город на Луне. На Давилоне есть собственная система метро, состоящая из N станций и M железнодорожных линий. Станции пронумерованы от 1 до N. Каждой линией управляет компания. У каждой компании есть идентификационный номер. I-я (1<=i<=M) линия соединяет станцию pi и qi двунаправленно. Промежуточной станции нет. Этой линией управляет компания ci . Можно делать пересадки на станции, где доступно несколько линий. Система оплаты проезда, используемая в этой системе метро, немного странная. Когда пассажир использует только те линии, которые обслуживаются одной и той же компанией, тариф составляет 1 сантик (валюта Давилона). Каждый раз, когда пассажир переходит на линию, которой управляет компания, отличная от текущей линии, с пассажира взимается дополнительная плата за проезд в размере 1 сантик. В случае, если пассажир, перешедший с линии компании А на линию другой компании, снова переходит на линию компании А, дополнительный тариф взимается снова. Незнайка сейчас на станции 1 и хочет добраться до станции N на метро. Найдите минимально необходимый тариф.
Входные данные
В первой строке задается два целых числа N (2<=N<=105) и M (0<=M<=2*105). В каждой из следующих M строк записаны по 3 числа: pi, qi и ci; 1<=pi<=N (1<=i<=M), 1<=qi<=N, 1<=ci<=106, pi ≠ qi.
Выходные данные
Выведите минимальный требуемый тариф. Если добраться до станции N на метро невозможно, выведите -1.
Примеры
| № |
Входные данные |
Выходные данные |
Пояснение |
| 1 |
3 3
1 2 1
2 3 1
3 1 2 |
1 |
Используйте линии компании 1:
1 → 2 → 3.
Стоимость проезда 1 сантик. |
| 2 |
8 11
1 3 1
1 4 2
2 3 1
2 5 1
3 4 3
3 6 3
3 7 3
4 8 4
5 6 1
6 7 5
7 8 5 |
2 |
Сначала используйте линии компании 1:
1 → 3 → 2 → 5 → 6.
Затем используйте линии компании 5:
6 → 7 → 8.
Стоимость проезда 2 сантика. |
| 3 |
2 0 |
-1 |
|
| |
![]()
|