Задача №112648. Финансирование
В стране Лимонии решили построить новые дороги между городами, используя совместное финансирование: строительство оплачивается из бюджетов тех городов, которые связываются данной дорогой.
Чтобы все было справедливо, доля городов-соседей в строительстве будет распределяться пропорционально доходам этих городов. Например, если строительство дороги стоит 5 млн рублей и она соединяет города А и Б с доходами 40 и 10 млн рублей соответственно, город А заплатит за строительство 4 млн рублей, а город Б – 1 млн рублей.
Если при расчётах вклада городов получаются нецелые числа, они округляются до целых так, что немного бОльшую часть доплачивает тот город, доход которого больше. При этом суммарный вклад двух городов не должен измениться.
Напишите программу, которая определяет общую стоимость строительства всех дорог в стране Лимонии и сумму, которую должен заплатить за это каждый город.
В первой строке вводится количество городов N ( 1 ≤ N ≤ 1000 ). В следующих N строках записано по N чисел, разделённых пробелами – элементы весовой матрицы графа, который описывает схему соединения городов дорогами. Числа в матрице обозначают стоимость строительства дороги между данными городами. В последней строке записано N чисел – годовые доходы каждого из городов.
В первой строке нужно вывести общую сумму, необходимую на строительство всех дорог. В следующей строке программа выводит через пробел N чисел – расходы каждого города.
5 0 10 15 22 0 10 0 6 0 18 15 6 0 38 0 22 0 38 0 14 0 18 0 14 0 100 560 120 300 290
123 12 26 20 53 12