I'm trying to solve 720B — Cactusophobia from Russian Code Cup 2016 Final. I read the editorial and understood the flow solution for this problem. So I find some implementation for this problem. I read dreamoon_love_AA's solution (20732895), which used Dinic flow finding algorithm and run in 373ms. But, since Dinic algorithm run in O(n2m), and the graph can have up to 30000 vertices and edges, how could this run in time? Can someone enlighten me about this? Thanks in advance.
→ Обратите внимание
До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
43:32:33
Зарегистрироваться »
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
43:32:33
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 21.11.2024 22:02:27 (i1).
Десктопная версия, переключиться на мобильную.
При поддержке
Sum of capacity of all edges is O(n). You can imagine an edge with capacity x as x edges with capacity 1. It'll be a unit graph, hence Dinic's algorithm will run in
.
Thanks for the clear explanation.
Dinic is min(fE, V^2E), and f <= V, so it is O(VE). (As above comment mentioned, tighter bounds are possible)