Лимит времени 1с.
Построили новую школу. Школа содержит N кабинетов, пронумерованных от 1 до N, между некоторыми из них двери. Когда ученик проходит через дверь, он получает определенное количество знаний. Вход в школу находится в кабинете 1, а выход в N. Каждый ученик проходит школу ровно один раз и поступает в определенный вуз в зависимости от набранных баллов (при входе в школу этот балл равен нулю). Ваша задача показать лучший результат.
Входные данные
Первая строка входного файла содержит целые числа N (1≤ N≤2000) — количество кабинетов и M (1≤M≤10000) количество дверей. В каждом из следующих M строк содержится описание двери: номер кабинета, из которого и в который они ведут, а также целое число, которое определяет количество знаний полученных при прохождении через дверь (это число по модулю не превышает 10000). Двери могут вести из кабинета в тот самый кабинет, между двумя кабинетами может быть больше чем одна дверь.
Исходные данные
В выходной файл выведите "yes" — если можно получить неограниченно большой запас знаний, "no" — если школу пройти нельзя, и максимальное количество знаний противном случае.
Что понятно:
1) задан ориентированный граф
2) если нет петель и циклов, граф — связный, тогда 1 — исток, N — сток, и решение получаем алгоритмом "нахождения максимального потока"
3) если есть петли или цикл(проверка алгоритмом bfs или dfs), где сумма по дугах положительна — тогда "yes"
4) если между 1 и N нет пути (алгоритм bfs или dfs), тогда "no".
Что вызывает вопрос: если применить все эти алгоритмы, то для "большого" графа предварительная проверка на ацикличность, проверка связности могут занять много времени. На чем можно (в рамках поставленной задачи) — сэкономить?
Здравствуйте, olimp_20, Вы писали:
_>Первая строка входного файла содержит целые числа N (1≤ N≤2000) — количество кабинетов и M (1≤M≤10000) количество дверей.
Наивное решение — это взять матрицу смежности, и возвести в степень >=N (можно в ближайшую степень 2 путём серии возведения в квадрат) в поле логмакс-умножения, с дополнительной обработкой циклов.
Только это довольно медленно. 12 возведений в квадрат матрицы 2000*2000.
Делать скидку на то, что матрица разрежена — в ней всего 10тыс дуг из 4млн — проблематично.
После возведения в квадрат она быстро перестанет быть разреженной.
_>3) если есть петли или цикл(проверка алгоритмом bfs или dfs), где сумма по дугах положительна — тогда "yes"
ИМХО граф ациклический и без петель.
Петля — это на второй год что ли остался ?
А цикл — это из 5-гог класса — обратно в третий?
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Здравствуйте, LaptevVV, Вы писали:
_>>3) если есть петли или цикл(проверка алгоритмом bfs или dfs), где сумма по дугах положительна — тогда "yes" LVV>ИМХО граф ациклический и без петель. LVV>Петля — это на второй год что ли остался ? LVV>А цикл — это из 5-гог класса — обратно в третий?
"В выходной файл выведите "yes" — если можно получить неограниченно большой запас знаний"
Эта оговорка заставляет полагать, что граф таки с циклами. Иначе как можно получить неограниченно большой запас знаний.
И таки да, повторения-матючения!
Здравствуйте, LaptevVV, Вы писали:
_>>3) если есть петли или цикл(проверка алгоритмом bfs или dfs), где сумма по дугах положительна — тогда "yes" LVV>ИМХО граф ациклический и без петель. LVV>Петля — это на второй год что ли остался ? LVV>А цикл — это из 5-гог класса — обратно в третий?
Как я понимаю, кабинет — не класс, а что-то по типу количества прослушанных часов на протяжении курса хотя это к делу не относится ... так что Кодт прав: повторение....
Здравствуйте, olimp_20, Вы писали:
_>Что вызывает вопрос: если применить все эти алгоритмы, то для "большого" графа предварительная проверка на ацикличность, проверка связности могут занять много времени. На чем можно (в рамках поставленной задачи) — сэкономить?
Получить подграф, состоящий только из путей от старта до финиша — не так уж долго.
Это забег за O(M) времени и O(N) памяти. Просто обходим граф вглубь, помечая встреченные вершины.
Тупики удаляем, откатываясь. Повторно встреченные вершины игнорируем. (Неважно, это точки слияния путей или циклы).
Убеждаемся, что есть хотя бы один путь до финиша. (Если нет, то останавливаемся и говорим NO).
После чего удаляем все непомеченные вершины.
Следующий обход вширь позволит нам найти самый длинный путь.
Будем сортировать вершины по возрастанию наибольшего расстояния от старта: заведём приоритетную очередь.
Начнём со стартовой вершины, с расстоянием s(1) = 0.
Берём самую ближнюю вершину V, берём все её смежные вершины V', находим/поправляем расстояния до них (s(V)+d(VV')) и кладём в очередь. Если V' уже в очереди, её расстояние может быть увеличено (s(V') := max(s(V'),s(V)+d(VV')), а сама она сдвинется дальше к хвосту.
После чего помечаем V как пройденную.
Если вдруг есть ребро из V в любую ранее пройденную вершину, либо в саму себя, это значит, что мы обнаружили цикл. Немедленно останавливаемся и говорим YES.
В конце концов в очереди должна остаться только вершина N с расстоянием s(N) от старта.
Раз у нас приоритетная очередь длиной O(N), то на каждом такте (вставка вершины, следующей по ребру из текущей) мы можем потратить O(log(N)) времени на переупорядочивание. А количество тактов, естественно, O(M) по числу рёбер.
То есть, на всё про всё уйдёт O(M * log(N)) времени.
Здравствуйте, Кодт, Вы писали:
К>Если вдруг есть ребро из V в любую ранее пройденную вершину, либо в саму себя, это значит, что мы обнаружили цикл. Немедленно останавливаемся и говорим YES.
Имхо, поспешный вывод, если ребро может иметь отрицательный вес. Например наличие цикла из двух ребер 5 и -10 приведет к бесконечной деградации, а не "yes".
На возможное наличие отрицательных весов указывает формулировка
целое число, которое определяет количество знаний полученных при прохождении через дверь (это число по модулю не превышает 10000)
Здравствуйте, olimp_20, Вы писали:
_>Что вызывает вопрос: если применить все эти алгоритмы, то для "большого" графа предварительная проверка на ацикличность, проверка связности могут занять много времени. На чем можно (в рамках поставленной задачи) — сэкономить?
Фактические имеем граф из N вершин (кабинетов) и M ребер (дверей). Каждому ребру присвоен вес (количество знаний). Нужно найти путь с максимальным весом. И похоже, что могут быть ребра с отрицательным весом.
Поэтому:
1. Меняем знак всех весов у ребер. Теперь нам надо уже искать путь с минимальным весом, т.е. искать кратчайший путь из вершины 1 в вершину N.
2. Т.к. веса могут быть разных знаков, то для поиска кратчайшего пути алгоритм Дейкстры не подойдет. А вот Алгоритм Беллмана — Форда такие случаи обрабатывать умеет (справится с циклами).
3. Худшее время работы алгоритма по времени O(M*N), т.е по условию задачи (десятки-сотни миллионов операций) должен уложиться в 1 сек.
Перекуём баги на фичи!
