|
Модераторы: Alx, Fixin |
|
Dmi3ev |
|
|||
Эксперт Профиль Группа: Завсегдатай Сообщений: 1698 Регистрация: 28.11.2007 Репутация: нет Всего: 41 |
подскажите логику рассуждений, за что зацепиться??? не могу понять пока... -------------------- |
|||
|
||||
maxdiver |
|
|||
Опытный Профиль Группа: Участник Сообщений: 381 Регистрация: 29.1.2008 Где: Саратов Репутация: 2 Всего: 18 |
Задача достаточно суровая.
Т.е., выкинув из условия "воду", задача сводится к такой: задан граф (т.е. набор точек-вершин, связанных отрезками-рёбрами), в котором каждое ребро либо не лежит в цикле, либо лежит только в одном цикле. Нужно "уложить" этот граф на плоскость, т.е. задать координаты его вершинам так, чтобы в результате никакие два ребра не пересекались. Такие графы, в которых каждое ребро принадлежит максимум одному циклу, называются кактусами (хотя как их называть, в общем-то, не важно). Выглядят они как-то так: Т.е. входной граф - это набор циклов, которые связаны между собой с помощью рёбер либо за счёт того, что два цикла имеют одну общую вершину. Причём если бы мы сжали все циклы в точки, то получится граф без циклов - так называемое "граф-дерево". Возможно, есть более простое решение, чем то, что я опишу ниже, но я не представляю, как эту задачу можно решать без честного разбора случаев. Моё решение более-менее простое идейно, но весьма сложно в написании (несколько часов написания в лучшем случае). Давайте теперь учиться решать задачу, т.е. укладывать наш кактус на плоскость. 1) Предположим, что в нашем входном графе нет циклов, т.е. он - дерево. Тогда укладывать его достаточно просто. Возьмём любую вершину как стартовую, поместим её в точку (0;0). Все вершины, связанные с ней, поместим на второй уровень: с y=1. Дальше, все вершины, связанные с вершинами первого уровня, поместим на второй уровень: y=2. И т.д. 2) Предположим теперь, что в графе есть один цикл. Найдём этот цикл, и выберем любую его вершину как стартовую, поместим её в точку (0;0). Остальные вершины цикла поместим над ней, т.е. на уровень y=1. Мы расположили цикл, теперь займёмся укладкой остального графа. Здесь уже всё становится относительно просто - мы пользуемся той же стратегией, что и в варианте 1), просто подвешивая остатки графа, прицепленные к каждой вершине цикла. Нам надо только следить за тем, чтобы деревья, привешенные к разным вершинами цикла, не перемешались друг с другом - иначе они начнут пересекаться. В общем, надо поступать как-то так: привесить всё ко второй вершине цикла, найти наибольший получившийся X, и сказать, что к третьей вершине мы будем подвешивать уже начиная с X+1. На рисунке я обвёл эти области оранжевым: Не забыть надо про то, что к стартовой вершине (той, которая в точке (0;0)), может быть также привешено что-то, и это надо будет привесить в последнюю очередь, после того, как мы обработали весь цикл. Опять же, привешиваем мы в такие иксы, чтобы быть гарантированно правее всего, что уже нарисовано. На рисунке я обвёл это фиолетовым: 3) Наконец, самый общий случай - т.е. в графе может быть сколько угодно циклов. К счастью, это не даёт ничего принципиально нового по сравнению с пунктом 2). Мы берём любой цикл, располагаем его, как описано в пункте 2), затем привешиваем к нему остальные части графа - опять же, как описано в части 2). Если в графе есть где-то другой цикл - ну обработаем его аналогично, т.е. просто поставим его не в (0;0), а в то место, где он окажется. Короче, говоря умным языком - после того, как мы поставили первый цикл в (0;0), оставшийся граф будем подвешивать рекурсивно. |
|||
|
||||
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей) | |
0 Пользователей: | |
« Предыдущая тема | Интересные и занимательные задачи по программированию | Следующая тема » |
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |