Is there a well known trick in max-flow, in which after entering a node or edge the flow through it multiplies by some constant k, which can be different for each node. Something like described in the image above.
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3985 |
| 2 | jiangly | 3814 |
| 3 | jqdai0815 | 3682 |
| 4 | Benq | 3529 |
| 5 | orzdevinwang | 3526 |
| 6 | ksun48 | 3517 |
| 7 | Radewoosh | 3410 |
| 8 | hos.lyric | 3399 |
| 9 | ecnerwala | 3392 |
| 9 | Um_nik | 3392 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 169 |
| 2 | maomao90 | 162 |
| 2 | Um_nik | 162 |
| 4 | atcoder_official | 161 |
| 5 | djm03178 | 158 |
| 6 | -is-this-fft- | 157 |
| 7 | adamant | 155 |
| 8 | awoo | 154 |
| 8 | Dominater069 | 154 |
| 10 | luogu_official | 151 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 23.12.2024 05:41:51 (l3).
Десктопная версия, переключиться на мобильную.
При поддержке
If you are just doing multiplications at each node rather than additions, you can just take the log of each weight and the problem is reduced to a normal max-flow. For example ln(a*k1) = ln(a)+ln(k1). So just solve the graph using logs, then your final answer e to the answer that you get from that process. (Though this of course introduces lots of rounding error and may not be acceptable for the application)
But by this method, i think every time you have two or more incoming edges, their net flow will multiply instead of adding, eg log(a) + log(b) = log(ab).
Ah, I was imagining finding 1 path at a time and then removing the used edges but I guess that general algorithms use augmenting paths, so having 2 incoming edges will be a problem. I'm not sure what you're talking about adding constant flow, unless you're talking about a different problem than max-flow... maybe I just don't understand the problem well enough without formal statement.
For example in the above picture, whenever an incoming flow(say a) flows through an vertex, than outgoing flow is increased by by constant k and becomes(a+k)(only when a is non-zero). As you said the problem doesn't actually comes under max-flow statement since incoming flow != outgoing flow for a non source-sink vertex, but i was wondering if it could be converted into one, through some other modeling.
Ok, I see what you mean more now. I don't think my method will work at all if addition is involved. I still am unclear about a few things of the statement though. Are we trying to maximize flow out of the source or into the sink? And when does constant flow get added? Is it just when you enter a node? Also, you say flow can be multiplied after entering a node or edge. One observation is that this is equivalent to just being multiplied after entering an edge (since we can just multiply the 'leaving a node' cost by the 'entering a node' cost).
Besides, can you share how you add an extra constant flow, whenever you enter a node(say A), ofcourse we can add an extra edge from source to node but that would increase the flow by the constant k, even when netflow through A was 0 previously, but that is undesired in my case.
I believe not. Find another modeling.
Thanks, i too was thinking of the same.