| Максимальное время работы на одном тесте: | 1 секунда |
Дан связный неориентированный граф без петель и кратных ребер. Разрешается удалять из него ребра. Требуется получить дерево.
Сначала вводятся два числа: N (от 1 до 100) и M – количество вершин и ребер графа соответственно. Далее идет M пар чисел, задающих ребра. Гарантируется, что граф связный.
Выведите N-1 пару чисел – ребра, которые войдут в дерево. Ребра можно выводить в любом порядке.
4 4 1 2 2 3 3 4 4 1
1 2 2 3 3 4
| Максимальное время работы на одном тесте: | 5 секунд |
Сначала вводится число N (1 <= N <= 100), а затем N чисел от 1 до 100 – элементы массива A[i]. Далее записаны два числа q и w (от 1 до N, не обязательно различные).
Требуется все элементы, которые равны A[q], сделать равными A[w]. Постарайтесь сначала считать данные, потом сделать то, что требуется, и только потом вывести результат (а не делать преобразование на этапе вывода). Постарайтесь не пользоваться допoлнительными массивами.
Выведите N чисел - элементы массива A[i] после преобразования.
5 1 4 2 2 5 3 2
1 4 4 4 5
| Максимальное время работы на одном тесте: | 5 секунд |
На вход программы поступает число N (от 2 до 100) и матрица смежности полного неориентированного взвешенного графа (полный граф – граф, в котором есть ребра между всеми парами вершин). Все веса ребер – натуральные числа от 1 до 1000. Далее дано N чисел, каждое из которых либо 0, либо 1 – считается, что эти числа записаны в вершинах. Гарантируется, что есть хотя бы один 0 и хотя бы одна 1.
Найдите и выведите такие две вершины, что:
3 0 1 2 1 0 4 2 4 0 1 0 0
2 1
| Максимальное время работы на одном тесте: | 5 секунд |
От вас требуется определить вес минимального остовного дерева для неориентированного взвешенного связного графа.
В первой строке входных данных находятся числа N и M (1 <= N <= 100; 1 <= M <= 6000), где N – количество вершин в графе, а M – количество рёбер. В каждой из последующих M строк записано по тройке чисел A, B, C, где A и B – номера вершин, соединённых ребром, а C – вес ребра (натуральное число, не превышающее 30000)
Вывести одно число – искомый вес.
3 3 1 2 1 2 3 2 3 1 3
3
| Максимальное время работы на одном тесте: | 2 секунды |
Рассмотрим таблицу размера MxN, в клетках которой стоят целые неотрицательные числа. Скажем, что таблица является симпатичной, если для всех i сумма чисел ее i-ой строки не превышает Ri, и для всех j сумма чисел ее j-го столбца не превышает Cj.
Вам задана таблица Z размера MxN, в некоторых клетках которой уже стоят целые неотрицательные числа. Найдите симпатичную таблицу с максимальной суммой элементов такую, что она совпадает с Z на тех клетках, в которых в Z стоят числа.
Первая строка входных данных содержит числа M и N (1 <= M, N <= 20). Следующая строка содержит M целых неотрицательных чисел - R1, R2, ..., RM. Далее идет срока, содержащая N целых неотрицательных чисел C1, C2, ..., CN. Все вводимые ограничения не превышают 106. Следующие M строк содержит по N целых чисел, которые задают Z. Если на некотором месте в таблице Z отсутствует число, то на этом месте во входных данных стоит -1.
Выведите найденную таблицу – M строк по N чисел. Если решения не существует, выведите единственное число -1.
2 2 1 10 1 10 -1 -1 -1 1
0 1 1 1