| Условие задачи | | |
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
|
| |
![]()
|