Оптимальное снабжение (НТО 23/24 :: ИЭС)

Легенда

Подзадача 1 (5 баллов).

В энергосистеме города Новоомулевск есть потребители и генераторы. У потребителей есть потребность в электроэнергии, а у генераторов — определённый объём произведённой энергии. Главному логисту города, Марии Ветровой, поручена задача составить план взаимодействия между генераторами для наименьших потерь энергии.

Марии известно расстояние от каждого потребителя до каждого генератора, объёмы выработанной энергии каждого генератора и объём спроса каждого потребителя. Необходимо удовлетворить потребителей, поставив им энергию, при этом необходимо сделать это максимально эффективно: чем дальше передаётся энергия, тем больше потерь.

Определите, сколько и кому каждый генератор должен передать энергии, чтобы минимизировать суммарные возможные потери при передаче. Гарантируется, что спрос можно удовлетворить полностью. Ваше решение должно обеспечивать такие же или меньшие суммарные возможные потери, как и авторское решение.

Формат входных данных: первая строка — два числа через пробел, количество генераторов N (до 7) и потребителей M (до 7). Во второй строке N чисел через пробел, объём предложения i-го генератора, в третьей строке аналогично M чисел – объём спроса i-го потребителя. Далее идёт матрица из N строк и M столбцов, где в элементе i-й строки и j-го столбца указывается расстояния между соответствующим генератором и потребителем. 

3 2
10 20 30
40 20
2 5
5 4
3 6

Формат выходных данных: аналогичная матрица, из N строк и M столбцов, где в элементе i-й строки и j-го столбца указывается объём передаваемой мощности от соответствующего генератора к соответствующему потребителю. Например,

2 5
5 4
3 6

Подзадача 2 (8 баллов).

Теперь решите эту задачу, но программным способом. Условия остаются те же.

Формат входных данных: первая строка — два числа через пробел, количество генераторов N (до 7) и потребителей M (до 7). Во второй строке N чисел через пробел, объём предложения i-го генератора, в третьей строке аналогично M чисел – объём спроса i-го потребителя. Далее идёт матрица из N строк и M столбцов, где в элементе i-й строки и j-го столбца указывается расстояния между соответствующим генератором и потребителем. Например,

3 2
10 20 30
40 20
2 5
5 4
3 6

Формат выходных данных: аналогичная матрица, из N строк и M столбцов, где в элементе i-й строки и j-го столбца указывается объём передаваемой мощности от соответствующего генератора к соответствующему потребителю. Например,

2 5
5 4
3 6

Time Limit: 5 секунд

Memory Limit: 256 MB

Для решения каждой подзадачи у вас есть 20 попыток.

Видео-разбор