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


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


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

 
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\)) и длина между ними 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  

 
ID 38655. Метро Давилона
Темы: Алгоритмы на графах    Кратчайшие пути в графе   

Давилон - самый крупный город на Луне. На Давилоне есть собственная система метро, состоящая из 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  

 
ID 33230. Школа
Темы: Минимальный каркас    Алгоритмы на графах   

С целью подготовки к проведению олимпиады по информатике мэр решил обеспечить надежным электроснабжением все школы города. Для этого необходимо провести линию электропередач от альтернативного источника электроэнергии “Майбуття” к одной из школ города (к какой неважно), а также соединить линиями электропередач некоторые школы между собой.
Считается, что школа имеет надежное электроснабжение, если она напрямую связана с источником “Майбуття”, либо с одной из тех школ, которые имеют надежное электроснабжение.
Известна стоимость соединения между некоторыми парами школ. Мэр города решил выбрать одну из двух наиболее экономичных схем электроснабжения (стоимость схемы равняется сумме стоимостей соединений пар школ).
 
Напишите программу, которая вычисляет стоимость двух наиболее экономных схем альтернативного электроснабжения школ.
 
Входные данные
В первой строке входного файла находятся два натуральных числа, разделенных пробелом: N (3 <= N <= 100), количество школ в городе, и M – количество возможных соединений между ними. В каждой из последующих M строк находятся по три числа: Ai, Bi, Ci, разделенных пробелами, где Ci - стоимость прокладки линии электроснабжения (1 <= Ci <= 300) от школы Ai до школы Bi (i=1,2,…,N).
 
Выходные данные
В единственной строке выходного файла должны содержаться два натуральных числа S1 и S2, разделенных пробелом – две наименьшие стоимости схем (S1 <= S2). S1=S2 тогда и только тогда, когда существует несколько схем надежного электроснабжения наименьшей стоимости.
 
Гарантируется, что для входных данных существует две различные схемы надёжного электроснабжения.
 
Примеры
№ Входные данные Выходные данные
1
5 8
1 3 75
3 4 51
2 4 19
3 2 95
2 5 42
5 4 31
1 2 9
3 5 66
 110 121