| | | |
|
Симпатичные таблицы
Алгоритм Форда-Фалкерсона
Рассмотрим таблицу размера 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.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
2 2
1 10
1 10
-1 -1
-1 1 |
0 1
1 1 |
| |
![]()
|
|
Мороженое
Алгоритм Форда-Фалкерсона
По дороге в школу Петя любит забегать в киоск и покупать себе мороженое. Однако при этом он часто опаздывает в школу. Неожиданно Петя понял - он просто ходит не по кратчайшему пути!
Помогите Пете победить опоздания. Город можно представить как N перекрестков, соединенных M улицами, про каждую улицу известна ее длина. Дом Пети находится на перекрестке A, школа - на перекрестке B, а киоск с мороженым - на перекрестке C. По пути в школу Петя никогда не проходит через один перекресток дважды.
Входные данные
Первая строка содержит числа N и M (3 ≤ N ≤ 30 000, 0 ≤ M ≤ 50 000). Вторая строка содержит три различных числа - A, B и C. Следующие M строк содержат по три целых числа Xi, Yi и Li - номера перекрестков, соединенных улицей и ее длину (длина - целое положительное число, которое не превышает 104).
Выходные данные
Если путь из дома Пети до школы, проходящий через перекресток с мороженым и не проходящий по одному перекрестку два раза, существует, выведите на первой строке выходного файла два целых числа K и L - количество улиц, которые проходит Петя в оптимальном пути и длину пути. На второй строке выведите номера перекрестков в том порядке, в котором их посещает Петя.
В противном случае выведите -1 на первой строке.
| |
![]()
|