Надо от вершины v до u найти реберно непересекающийся путь минимального веса.
Веса на ребрах могут быть отрицательными.
Умею делать за m * m. Надо быстрее.
Помогите пожалуйста!
→ Обратите внимание
До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
07:00:10
Зарегистрироваться »
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
07:00:10
Зарегистрироваться »
*есть доп. регистрация
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 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 | 156 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 23.11.2024 10:34:51 (h1).
Десктопная версия, переключиться на мобильную.
При поддержке
Автокомментарий: текст был обновлен пользователем skrydg (предыдущая версия, новая версия, сравнить).
Хм... А ведь это не совсем то же самое, что найти единичный поток минимального веса. Но явно что-то связанное. А как за m*m искать?
Строим новый граф, где вершины это ребра, а ребра вершины ;)
И там уже просто дфс.
А граф вообще ориентированный или нет?
Да, граф ориентированный
Еще один тупой вопрос: откуда берется оценка m2? На мой взгляд, можно все ребра посоединять за n * m: идем по каждой вершине, пусть ее степени a[v] на вход и b[v] на выход. Тогда соединить все ребра, которые входят в вершину, можно за a[v] * b[v]. Сумма всех a[v] не превосходит m, каждое b[v] ограничено сверху n. Итого m * n.
Да, косяк.
Задача коммивояжёра, казалось бы, сводится к этой. Пусть все длины рёбер в задаче коммивояжёра от нуля до W. Сделаем из каждого ребра с весом x ребро с отрицательным весом x - nW. Теперь решение задачи из поста является также решением задачи коммивояжёра: из-за добавки - nW в оптимальном решении, очевидно, будут пройдены все вершины, а сумма исходных весов x будет минимизирована.
UPD: Это сведение неверно. Было бы верно для вершинно-непересекающихся путей. А тут рёберно-непересекающиеся. Тем не менее, задача выглядит для меня как не решаемая за полином... как её решать за m × m?
Строим новый граф. Где вершины это ребра. Вершины a и b соединим ребром, если конец а совпадает с началом b(здесь a и b это номера ребер).
Теперь у нас есть ориентированный граф, где у каждой вершины есть стоимость. Нам нужно найти кратчийшее расстояние от множества вершин, до другого множества(от всех исходящих ребер, до всех входящих), причем тут мы рассматриваем вершинно не пересекающиеся пути. Это делается дейкстрой. С асимптотикой m * m я конечно налажал. (Сверху это уже написали).
Непонятно как это помогает, стоимости вершин(а значит и веса ребер) могут быть отрицательными.
Ребра могут иметь отрицательные веса. Но ведь дейкстра с потенциалами найдет кратчайший путь.
Это если нет цикла отрицательного веса
Дейкстра с потенциалами не ищет вообще ничего, если нет потенциалов.
Кажется, ответ тут: http://cstheory.stackexchange.com/questions/20682/is-the-longest-trail-problem-easier-than-the-longest-path-problem
Кажется, можно свести "longest path problem in directed graph" к этой, просто заменив каждую вершину на две (одна для входа, вторая для выхода). Тогда между вершинно-непересекающимися (в изначальном графе) и реберно-непересекающимися (в графе с удвоенными вершинами) будет биекция.
И то, и другое похоже на правду. Спасибо!