Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 
[Вернуться к задаче]   1
  1  Бончев Максим Владимирович, 01 сентября 2019 г. 21:34:27
     Денис, это не важно. Главное что б все условия прапорщика были соблюдены.
  2  Маркелов Денис Дмитревич, 09 февраля 2018 г. 12:07:55
     тесты показывают, что достаточно проверить на ацикличность, а как 3 2 1 2 3 2 Кто выше 1 или 3 ?
  3  Зинов Вадим Игоревич, 10 октября 2014 г. 23:11:59
     Луффи, спасибо за упоминание о "черных точках" очень помогло.
  4  Луффи, 07 октября 2014 г. 17:19:31
     Изначально все вершины «белые». Из каждой вершины проводим обход в глубину.

При входе в вершину делаем её «серой», при выходе — «чёрной» и одновременно заносим в окончательный список.
Если вдруг вошли в серую вершину — найден цикл, топологическая сортировка невозможна.
  5  Захаров Константин Леонидович, 05 декабря 2013 г. 18:09:43
     Топсорт с емакса конечно копируется неплохо, но, чисто для справки - можно еще фордом беллманом, правда уже несовсем так, как на емаксе) Кстати, кто хочет прикрутить восстановление ответа и нитащит - попробуйте тест
5 4
1 2
3 2
3 4
5 4
у меня вообще выводило 1 2 3 4 5 с первоначальной версией (бфс из вершин где parent[v] == -1), но удалось пофиксить.
  6  Настенька, 19 ноября 2012 г. 15:24:09
     А что за наркоманские решения: искать циклы, топологическую сортировку использовать? Тут всё намного проще и завязано на одном из легчайших алгоритмов на графах (спойлерить уж не буду)
     Куда еще проще? Поделитесь с народом.
  7  Настенька, 19 ноября 2012 г. 15:23:00
     С первого раза минут за десять. Воохууу, сегодня мой день
  8  Гераськин Егор Владимирович, 29 сентября 2012 г. 22:59:51
     Тупо проверка графа на ацикличность:)
     Да
  9  Сафронов Евгений Сергеевич, 09 июля 2012 г. 7:43:35
     Распространённая задача на топологическую сортировку — следующая. Есть n переменных, значения которых нам неизвестны. Известно лишь про некоторые пары переменных, что одна переменная меньше другой. Требуется проверить, не противоречивы ли эти неравенства, и если нет, выдать переменные в порядке их возрастания (если решений несколько — выдать любое). Легко заметить, что это в точности и есть задача о поиске топологической сортировки в графе из n вершин.

=)
Но про искать циклы - верно. Невозможно составить топологическую сортировку, если в графе есть циклы. Но нам нужна не сама сортировка, а лишь проверка на ее возможность, так что 62% - многовато...
     Согласен, процент завышен. Но не сильно. Всякая задача с рекурсией - это минимум 45% на данном сайте.
  10  Терешин Роман Юрьевич, 21 марта 2012 г. 13:56:28
     В 12 тесте (возможно, и в других также) входные данные допускают повтор пар. В терминах задачи это означает, что прапорщик о некоторых парах солдат знает одно и тоже несколько раз - удивительная вещь (одновременное присутствие упорядоченной пары и пары, ей обратной в виду не имеется - это вполне корректная ситуация, ответ на вход, содержащий подобное - "No"). Для реализации это означает следующее - если вы выбираете список смежности для представления графа в памяти, а каждый из списков реализуете массивом, "знающим" свой размер - учтите, что при получении входных данных вы можете столкнуться с тем, что вершина может иметь более N - 1 соседей - камень в огород составителей тестов.
  11  Жиркевич Анастасия Борисовна, 01 февраля 2012 г. 23:35:28
     Кто еще думает, каким алгоритмом воспользоваться, рекомендую алгоритм ФЛОЙДА-УОРШЕЛЛА. Находка Википедии... просто супер - короче алготма я еще не видела. А на ацикличность проверку сделать легко: проверьте есть ли на диагонали не нули))) и ACCEPTED
     Возможно, если искать не наикратчайшие расстояния, а наидлиннейшие.
  12  Балакший Андрей Владимирович, 24 октября 2011 г. 20:56:41
     Все таки делал по-честному, при отправке лишь закомментил вывод топ.сортировки. Но все равно много процентиков, даже слишком....
  13  Пересадин Илья, 26 августа 2010 г. 19:25:07
     интересней было бы, если бы требовалось вывести построение... а то можно просто на ацикличность проверить и не париться
  14  Ким Вячеслав Олегович, 06 февраля 2010 г. 14:02:56
     Надо бы задачу, чтоб все построение выводить надо было.
  15  Демиденко Виталий, 15 марта 2009 г. 20:11:22
     Если есть цикл, то No, иначе построение возможно. С таким решением прошло.
  16  Akzholov Darhan Bektenovich, 07 марта 2008 г. 21:10:00
     А что если искать циклы? Если есть цикл то - NO else YES ?
     Да, можно.
  17  Беляев Игорь (<-UnderFelixAbove->) 21 год, 19 января 2008 г. 1:28:55
     Топологическая сортировка нынче в цене).
     Да, типа того.
 1

Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!

Красноярский краевой Дворец пионеров, (c)2006 - 2020, E-mail: admin@acmp.ru