Думаю, куплю собі футбольну команду
Falling Stocks. Збанкрутілі компанії. Банки без готівки. Здається, найкращий час для інвестицій: "Думаю, куплю собі футбольну команду!"
Ні, серйозно, я думаю, що маю рішення принаймні для проблеми з готівкою в банках. Сьогодні банки всі винні один одному великі суми грошей, і жоден банк не має достатньо готівки, щоб сплатити борги інших банків, хоча, принаймні на папері, вони повинні мати достатньо грошей для цього. Візьмемо, наприклад, міжбанківські кредити, показані на рисунку (а). Графік показує суми, які винні один одному чотири банки (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 (з A's 100M) безпосередньо C. Це зменшує графік до того, що показано на рисунку (c). Банки можуть врегулювати всі свої борги лише з 120M готівкою. Загальне зменшення на 260M або 68%. Дивовижно!
У мене є дані про міжбанківські борги, але я не можу їх обробити, щоб отримати мінімальну суму готівки, необхідну для врегулювання всіх боргів. Чи могли б ви написати програму для цього?
Вхідні дані
Ваша програма буде протестована на одному або більше тестових випадках. Кожен тестовий випадок задається на N+1 рядках, де N < 1000 — це кількість банків і вказується на першому рядку. Решта N рядків задають міжбанківські борги за допомогою N×N матриці суміжності (з нульовою діагоналлю), заданої в порядку рядків. i-й рядок вказує суми, які винен i-й банк. Суми розділені одним або більше пробілами. Останній рядок вхідного файлу містить одну цифру 0.
Вихідні дані
Для кожного тестового випадку виведіть результат у наступному форматі:
k. B A
де k — це номер тестового випадку (починаючи з 1), пробіл, B — сума готівки, необхідна до зменшення, і A — сума готівки після зменшення.