Думаю, куплю себе футбольную команду
Падающие акции. Обанкротившиеся компании. Банки без наличных. Кажется, самое время для инвестиций: "Думаю, куплю себе футбольную команду!"
Нет, серьезно, у меня есть идея, как решить проблему нехватки наличных в банках. Сегодня банки должны друг другу огромные суммы, и ни у одного из них нет достаточно наличных, чтобы погасить долги перед другими банками. Хотя, по крайней мере на бумаге, у них должно быть достаточно средств для этого. Рассмотрим пример межбанковских кредитов, показанный на рисунке (а). График иллюстрирует задолженности между четырьмя банками (A...D). Например, A должен B 50M, в то время как B должен A 150M. (Часто бывает, что два банка одновременно должны друг другу). Для урегулирования всех долгов между банками требуется общая сумма в 380M наличными.
Пытаясь уменьшить потребность в наличных, и после внимательного изучения примера, я пришел к выводу, что много наличных переводится без необходимости. Посмотрите:
C должен D столько же, сколько D должен A, поэтому мы можем сказать, что C должен A сумму в 30M и исключить D из картины.
Но поскольку A уже должен C 100M, мы можем сказать, что A должен C сумму в 70M.
Аналогично, B должен A только 100M, (поскольку A уже должен B 50M). Это сокращает приведенный выше график до того, что показан на рисунке (b), что уменьшает необходимую сумму наличных до 190M (A сокращение на 200M, или 53%).
Я могу сделать еще лучше. Вместо того чтобы B платил A 100M и A платил 70M C, B может заплатить 70M (из 100M A) напрямую C. Это сокращает график до того, что показан на рисунке (c). Банки могут урегулировать все свои долги всего с 120M наличными. Общее сокращение на 260M или 68%. Удивительно!
У меня есть данные о межбанковских долгах, но я не могу обработать их, чтобы получить минимальную сумму наличных, необходимую для урегулирования всех долгов. Не могли бы вы написать программу, чтобы сделать это?
Входные данные
Ваша программа будет тестироваться на одном или нескольких тестовых случаях. Каждый тестовый случай задается на N+1 строках, где N < 1000 — это количество банков, указанное в первой строке. Оставшиеся N строк задают межбанковские долги с использованием N×N матрицы смежности (с нулевой диагональю), заданной в порядке строк. i-я строка указывает суммы, которые должен i-й банк. Суммы разделены одним или несколькими пробелами. Все суммы меньше 1000. Последняя строка входного файла содержит одну цифру 0.
Выходные данные
Для каждого тестового случая напечатайте результат в следующем формате:
k. B A
где k — номер тестового случая (начиная с 1), пробел, B — сумма наличных, необходимая до сокращения, и A — сумма наличных после сокращения.