Всем привет, ребят подскажите. Как найти k самых длинных путей в неориентированном графе (ребра равны 1)? Заранее спасибо.
→ Обратите внимание
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3857 |
| 2 | jiangly | 3810 |
| 3 | maroonrk | 3534 |
| 4 | tourist | 3528 |
| 5 | Kevin114514 | 3510 |
| 6 | turmax | 3411 |
| 7 | Um_nik | 3387 |
| 8 | Radewoosh | 3367 |
| 9 | heuristica | 3322 |
| 10 | strapple | 3317 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 157 |
| 2 | maspy | 150 |
| 3 | nik_exists | 148 |
| 4 | Um_nik | 145 |
| 5 | Errichto | 139 |
| 6 | adamant | 136 |
| 7 | maroonrk | 134 |
| 8 | BledDest | 133 |
| 9 | DNR | 132 |
| 9 | AmShZ | 132 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2026 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 09.09.2026 15:19:10 (g2).
Десктопная версия, переключиться на мобильную.
При поддержке
Уже найти один самый длинный простой путь само себе NP-трудная задача. Уточните условие.
Чтобы найти один самый длинный простой путь, можно ведь N раз запустить bfs из всех вершин. Получится асимптотика O(NM). Разве это NP-трудная задача?
Эта задача эквивалентна задаче о гамильтоновом пути http://en.wikipedia.org/wiki/Hamiltonian_path_problem
Ну-ну. BFS, позвольте напомнить, ищет кратчайшие пути из одной вершины до всех. Вы просто найдёте самый длинный из кратчайших путей между парой вершин.
Понял свою ошибку, спасибо.
Достижимость всех вершин с какой то одной, которую получим в BFS, не означает, что можно через них построить простой путь. http://en.wikipedia.org/wiki/Longest_path_problem
Нужно найти 3 самых длинных путя, число вершин 2400, количество рёбер 4500, при этом он разделён на несколько компонент связности, в каждой из которых не более 250 вершин.