Комментарии 16
„То есть если маршрут от одного города до другого имеет как дороги типа R, так и дороги типа B, то ни один поезд не сможет проехать по этому маршруту“ вы тут не опечатались?
Если это условие верно, то проблема с этим:
«Карта железных дорог называется оптимальной, если не существует пары городов A и B такой, что от A до B
можно добраться как по дорогам типа R, так и по дорогам типа B.
Иными словами, для любой пары городов верно, что от города с меньшим номером до города с бо́льшим номером можно добраться по дорогам только какого-то одного типа или же что маршрут построить вообще нельзя.»
В этом случае граф надо упростить, выбросив все дороги где А-Б имеют и R и B дорогу.
Было бы лучше если бы вы оригинальную задачу изложили , “как она была отцами основателями» придумана, а не позднейшую интерпретацию
„То есть если маршрут от одного города до другого имеет как дороги типа R, так и дороги типа B, то ни один поезд не сможет проехать по этому маршруту“ вы тут не опечатались?
Нет, тут всё верно. Подразумевается конкретный маршрут как последовательность ребер.
Но эти строки лучше выкинуть из условия, это очевидное следствие из поинта "Любой поезд может ездить только по одному типу полотна" и оно лишь словесно засоряет условие, без пользы.
надо найти из города А в город Б дорогу по которой можно проехать, и город А и город Б могут гдето находится на граффе, мне кажется надо найти из города А все восходящие дороги - отрезки типо, а вторым подходом отсеч разноцветные если не останется действенных вывести дорог нет, наверно так, простите если это капитан очевидность
Только это тоже можно по-разному делать. Можно алгоритмом Флойда(неэффективно), а можно поиском в ширину/глубину.
по алгоритмам наверно я просто представил себя на месте пользователя
(типо хочу сказать что я в городе А значит от него надо простраивать отрезки одноцветные, может в глубину ага)
давайте немного ее изменим но условие останется тем же, в игре есть точки полётов и система автопути из городов до городов, мы должны простроить 1 маршрут из точки где игрок в виртуальном мире, наверно оно, тоесть это интерактивный запрос до точки какойто причем если игрок выбрал точку где он ему надо сказать что он в этой точке
получится или летим или бежим автопутём
(и по условию цвет дороги 1 и прочее и прочее)
Немного другое решение (на самом деле близкое к поиску циклов, потому как их очень похожим образом можно искать).
Сначала делаем обход в глубину с отметаками времени входа-выхода для дорог одного типа.
Это позволяет за O(1) отвечать на вопрос "является ли эта вершина предком этой", что для нашего графа эквивалентно "если ли из первой ж/д первого типа во вторую".
Дальше делаем обход по железным дорогам второго типа, но проверяем соединённость по первому типу при помощи отметок времени.
Но ведь граф не обязательно будет деревом. Он будет каким-то DAG. Например, добавьте в ваш граф на картинке ребра из F в E и из E в С. И попробуйте тут за O(1) определить, достижима ли C из F.
Поправьте, если ошибаюсь, но дерево будет в любом случае, ведь мы можем двигаться только к тем узлам, чье значение больше исходного
Ну нет же. 1->2, 1->3, 2->4, 3->4. Движение только к большим. Но это не дерево, если вы это нарисуете, у вас получится ромб. У вершины 4 2 предка, чего в дереве быть не может.
Движение только к большим задает лишь ацикличность графа.
Можно еще сослаться на размернось.
В дереве `V - 1` ребро. В этом графе V * (V - 1) / 2 ребер
Поскольку в графе есть пути между каждой парой вершин
Этого вы в условии не указали.
если маршрут от одного города до другого имеет как дороги типа R, так и дороги типа B, то ни один поезд не сможет проехать по этому маршруту
Это условие нарушается, если это два соседних города. В условии не сказано, что между двумя соседними городами может только одна дорога одного типа. Может ведь быть и две дороги? Как в игре Brass между городами бывают речные каналы, бывают железные дороги, но зачастую есть и то, и другое вместе. Чтобы не путаться с шириной дорог, можно было также написать. Мол, нужно доехать из точки отправления в точку назначения не сходя с поезда, либо не сходя с корабля, без пересадок.
Алгоритмы из теории графов: решаем сложную задачу из курса Яндекс Практикума