| | | |
|
Количество дорог
Алгоритмы на графах
Напишите программу, которая считает количество дорог в городе Новые Васюки. Схема дорог задана как матрица смежности графа. На некоторых дорогах введено одностороннее движение.
Входные данные
В первой строке вводится количество перекрёстков в Новых Васюках 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<=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 |
| |
![]()
|
|
Города и дороги
Алгоритмы на графах
В галактике "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 |
| |
![]()
|
|
Суммарная длина дорог
Алгоритмы на графах
Найдите суммарную длину всех дорог в городе Новые Васюки. Схема дорог задана в виде весовой матрицы графа. На некоторых дорогах введено одностороннее движение. Если длины дорог из пункта А в пункт Б разные, это означает, что есть две разные дороги.
Входные данные
В первой строке вводится количество перекрёстков в Новых Васюках 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 |
| |
![]()
|
|
Светофорчики-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 |
| |
![]()
|
|
Проверка на неориентированность
Алгоритмы на графах
По заданной квадратной матрице 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, – его матрицу смежности.
Выходные данные: Выведите список ребер заданного графа (в любом порядке).
| № |
Входные данные |
Выходные данные |
| 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 (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 |
| |
![]()
|