Your text to link here... My logic is as follows: First of all, we can get all the SCC's of the graph with their respective sums. Now we can make a condensed graph sort of thing, where each SCC acts as a node. I'm not able to get what to do after that? I gave a hard thought of maintaining DP after that but couldn't get on with the recurrence relations. Any help would be appreciated.
→ Обратите внимание
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 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 | 164 |
| 1 | maomao90 | 164 |
| 3 | Um_nik | 163 |
| 4 | atcoder_official | 160 |
| 5 | -is-this-fft- | 158 |
| 5 | adamant | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 8 | nor | 154 |
| 10 | djm03178 | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 13.11.2024 06:30:48 (l1).
Десктопная версия, переключиться на мобильную.
При поддержке
As you might have guessed that if we add SCC to our final result, the whole value of that SCC will get added. Further, what we can now do is for each SCC, we find out how many other SCC's it can visit. Here we will call a DFS so that only once we add a particular node value to its corresponding DP. That would mean dp[i] = sum of dp[adjacent nodes from i] + current node value DFS will take care that you don't add a value multiple times.