Плюсануть
Поделиться
Класснуть
Запинить

Задачи из рубрикатора

Тег: Алгоритмы на графах

Условие задачи  
ID 33226
Количество дорог
Темы: Алгоритмы на графах   

Напишите программу, которая считает количество дорог в городе Новые Васюки. Схема дорог задана как матрица смежности графа. На некоторых дорогах введено одностороннее движение.
 
Входные данные
В первой строке вводится количество перекрёстков в Новых Васюках 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

ID 33227
Суммарная длина дорог
Темы: Алгоритмы на графах   

Найдите суммарную длину всех дорог в городе Новые Васюки. Схема дорог задана в виде весовой матрицы графа. На некоторых дорогах введено одностороннее движение. Если длины дорог из пункта А в пункт Б разные, это означает, что есть две разные дороги.
 
Входные данные
В первой строке вводится количество перекрёстков в Новых Васюках 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

ID 22017
Города и дороги
Темы: Алгоритмы на графах   

В галактике "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

ID 22018
Светофорчики-1
Темы: Алгоритмы на графах   

В подземелье 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
 

ID 22019
Цветной дождь
Темы: Алгоритмы на графах   

В Банановой республике очень много холмов, соединенных мостами. На химическом заводе произошла авария, в результате чего испарилось экспериментальное удобрение "зован". На следующий день выпал цветной дождь, причем он прошел только над холмами, в некоторых местах падали красные капли, в некоторых -  синие, а в остальных - зеленые, в результате чего холмы стали соответствующего цвета. Президенту Банановой республики это понравилось, но ему захотелось покрасить мосты между вершинами холмов так, чтобы мосты были покрашены в цвет холмов, которые они соединяют. К сожалению, если холмы разного цвета, то покрасить мост таким образом не удастся.
Посчитать количество таких "плохих" мостов.
 
Входные данные: 
- в первой строке записано 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
 

ID 33130
Проверка на неориентированность
Темы: Алгоритмы на графах   

По заданной квадратной матрице 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

ID 33129
Петли
Темы: Алгоритмы на графах   

По заданной матрице смежности неориентированного графа определите, содержит ли он петли.
 
Входные данные: 
- в первой строке задается число 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

ID 33131
От матрицы смежности к списку ребер, неориентированный вариант
Темы: Алгоритмы на графах   

Простой неориентированный граф задан матрицей смежности, выведите его представление в виде списка ребер.
 
Входные данные: входные данные включают число 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

ID 33132
От списка ребер к матрице смежности, неориентированный вариант
Темы: Алгоритмы на графах   

Простой неориентированный граф задан списком ребер, выведите его представление в виде матрицы смежности.
 
Входные данные: 
- в первой строке задаются числа 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 

ID 38444
Деревни
Темы: Динамическое программирование    Алгоритмы на графах    Обход в глубину    Динамическое программирование на графах   

В тридесятом государстве есть 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.

ID 38512
Шоссе и дороги
Темы: Алгоритмы на графах   

Есть 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  

 

ID 38516
Петербург?
Темы: Интерактивные задачи    Мосты    Алгоритмы на графах   

– Это что за остановка – Бологое иль Поповка? – А с платформы говорят: – Это город Ленинград.
«Вот какой рассеянный», Самуил Маршак
Пытаясь спастись от мира спортивного программирования, Алина сбежала на вокзал и уехала прочь на ночной электричке. Минуты медленно уплывали в даль, и уставшую девочку клонило в сон. Ей снился город-сказка, где не надо программировать, а можно гулять, мечтать и наслаждаться жизнью. Внезапно дождь из интерактивных задач разрушил эту идиллию.

Проснувшись и открыв окно, Алина задалась вопросом весьма философского свойства: «Где я?». С перрона потерявшейся девочке сообщили, что этот город, не похожий ни на что вокруг, представляет собой неориентированный граф на 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

ID 38521
Кандидаты в не кратчайший путь
Темы: Алгоритмы на графах    Кратчайшие пути в графе   

Дан неориентированный связный взвешенный граф с 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, bici (\(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
Каждое ребро содержится в некотором кратчайшем пути между парой различных вершин.

 

ID 38585
Транзитный путь
Темы: Алгоритмы на графах    Кратчайшие пути в графе    Обход в ширину   

Вам дано дерево с 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\)) и длина между ними c(\(1<=c_i<=10^9\)\(1<=i<=N-1\))
Далее идут два числа Q и(\(1<=Q<=10^5\)\(1<=K<=N\)). В последних Q строках записаны целые числа xjy(\(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