сетевое решение задачи назначения потока

Question

У меня проблема назначения с матрицей затрат C, например:

21 30 26 16 20
27 29 28 20 38
39 25 21 19 23
28 24 30 29 16
30 33 32 17 31

где C [i] [j] означает затраты для работника i на работу j.

Как я могу решить эту проблему с помощью алгоритма сетевого потока? Буду рад любым подсказкам.

Answer 1

Если вы все еще ищете решение, вы можете решить его как Задача с минимальными затратами :

1. Создать исходный узел, подключенный к вашим N работникам, с помощьюребра с емкостью 1 и стоимостью 0
2. Подключите каждого работника i к каждому заданию j по ребрам емкости 1 и стоимостью C [i] [j]
3. Наконец подключите каждое задание к узлу приемника с помощьюграницы емкости 1 и стоимости 0

Ваша задача эквивалентна минимизации затрат на передачу N потоковых единиц через сеть от источника к приемнику.