Is it possible to recover the flow for each edge after running the Push-relabel algorithm on a graph?
It seems like some inside cycles of flow can exist after running the algorithm.
Is it possible to recover the flow for each edge after running the Push-relabel algorithm on a graph?
It seems like some inside cycles of flow can exist after running the algorithm.
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3611 |
| 4 | jiangly | 3583 |
| 5 | strapple | 3515 |
| 6 | tourist | 3470 |
| 7 | dXqwq | 3436 |
| 8 | Radewoosh | 3415 |
| 9 | Otomachi_Una | 3413 |
| 10 | Um_nik | 3376 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 158 |
| 2 | adamant | 152 |
| 3 | Um_nik | 146 |
| 4 | Dominater069 | 144 |
| 5 | errorgorn | 141 |
| 6 | cry | 139 |
| 7 | Proof_by_QED | 136 |
| 8 | YuukiS | 135 |
| 9 | chromate00 | 134 |
| 9 | TheScrasse | 134 |
There is some optimization for the push-relabel algorithm which only guarantees the answer to be preflow, not actual flows. To recover the solution, you should run flow decomposition or just get rid of this optimization. I think flow decomposition can be slow, so you should just generally don't have this optimization.
Here is the implementation without that optimization.
I was just reading through the implementation, and read a comment in it that said
basic_stringis bad for this specific use-case. Any idea why that might be the case (I've never faced any issue with usingbasic_stringfor graphs — weighted or unweighted)?Well, it did something unbelievable, but I don't remember what it was. I think you can look up for C++ documentation to guess what it is.
What's the complexity without the optimization? I'm thinking of just using Dinic instead.
Complexity remains same: $$$O(V^2 \sqrt E)$$$. Even without the optimization, HLPP is still fast enough empirically.