Hi. We all know algorithms that find maximal flow, but is there an algorithm that finds minimum flow? For example let's take the following task: Given N workers and N jobs. Each worker takes different amount of money for doing each job and each job can be done by only one worker. Assign the workers to the jobs, so as to the sum of money is minimum. P. S. Apart from using Hungarian algorithm, is there another way?
→ Обратите внимание
До соревнования
Refact.ai Match 1 (Codeforces Round 985)
4 дня
Зарегистрироваться »
Refact.ai Match 1 (Codeforces Round 985)
4 дня
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3831 |
| 3 | Radewoosh | 3646 |
| 4 | jqdai0815 | 3620 |
| 4 | Benq | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | gamegame | 3386 |
| 10 | ksun48 | 3373 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 164 |
| 1 | maomao90 | 164 |
| 3 | Um_nik | 163 |
| 4 | atcoder_official | 160 |
| 5 | -is-this-fft- | 158 |
| 6 | awoo | 157 |
| 7 | adamant | 156 |
| 8 | TheScrasse | 154 |
| 8 | nor | 154 |
| 10 | Dominater069 | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 05.11.2024 17:03:26 (i1).
Десктопная версия, переключиться на мобильную.
При поддержке
Min Cost Max Flow
Change the cost ci of every edge to cmax - ci. Then, it becomes an algorithm for maximum flow.
In fact, minimal flow is 0, but it's not (I guess) what you're asking about.
What you really need is the min-cost flow algorithm, which is quite similar to Ford-Fulkerson algorithm: the difference is only that you search augmenting paths using not DFS, but any shortest-paths algorithm (like Ford-Bellman) that allows weights to be negative (in this case, weights are the costs of the edges).