Модераторы: Alx, Fixin
  

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Задача про компьютерную сеть для детей 
:(
    Опции темы
Dmi3ev
Дата 20.10.2011, 17:36 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


Профиль
Группа: Завсегдатай
Сообщений: 1698
Регистрация: 28.11.2007

Репутация: нет
Всего: 41



Цитата

Для проведения олимпиады школьников по информатике требуется соединить компьютеры в сеть. Организаторы олимпиады разработали схему соединения компьютеров. В соответствии с этой схемой некоторые пары компьютеров должны быть соединены кабелем, и сигнал сможет дойти по кабелям от любого компьютера до любого другого, возможно, через другие компьютеры.

Некоторые компьютеры могут быть соединены циклически. Цикл называется простым, если каждый компьютер из этого цикла соединён ровно с двумя другими компьютерами этого цикла, и в этот цикл никакой кабель не входит более одного раза. Некоторые кабели могут не входить ни в какой цикл.

Известно, что в разработанной схеме никакой кабель не принадлежит двум простым циклам одновременно.

Организаторам олимпиады поручено разместить компьютеры в зале соревнований. При размещении должны выполняться следующие условия:

1.     Компьютеры размещаются на плоскости в точках с целочисленными координатами.

2.     Координаты компьютеров x и y лежат в диапазоне 0 ≤ x, y ≤ 106.

3.     Никакие два компьютера не располагаются в одной точке.

4.     Кабели являются отрезками прямых.

5.     Кабели не пересекаются между собой и не проходят через точки размещения компьютеров, к которым они не подключены.

Требуется написать программу, выполняющую размещение компьютеров по заданному описанию схемы.

Формат входных данных
В первой строке входного файла содержатся числа N и M — количество компьютеров и количество кабелей в схеме (1 ≤ N ≤ 100 000, 0 ≤ M ≤ 200 000). В последующих M строках содержатся пары чисел, разделенных пробелами. Каждая такая пара описывает один кабель, числа представляют собой номера соединенных компьютеров. Компьютеры пронумерованы от 1 до N. Никакая пара не встречается дважды, и никакой кабель не соединяет компьютер с самим собой.

Формат выходных данных
Выходной файл должен содержать N строк. Строка с номером i должна содержать координаты i-го компьютера, разделенные пробелом. Сначала выводится координата x, затем y. Разрешается вывести любой вариант размещения компьютеров, при котором выполняются условия 1–5.


подскажите логику рассуждений, за что зацепиться??? не могу понять пока... smile  smile  smile 


--------------------

PM MAIL   Вверх
maxdiver
Дата 28.10.2011, 12:02 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 381
Регистрация: 29.1.2008
Где: Саратов

Репутация: 2
Всего: 18



Задача достаточно суровая.

Т.е., выкинув из условия "воду", задача сводится к такой: задан граф (т.е. набор точек-вершин, связанных отрезками-рёбрами), в котором каждое ребро либо не лежит в цикле, либо лежит только в одном цикле. Нужно "уложить" этот граф на плоскость, т.е. задать координаты его вершинам так, чтобы в результате никакие два ребра не пересекались.

Такие графы, в которых каждое ребро принадлежит максимум одному циклу, называются кактусами (хотя как их называть, в общем-то, не важно). Выглядят они как-то так:

user posted image

Т.е. входной граф - это набор циклов, которые связаны между собой с помощью рёбер либо за счёт того, что два цикла имеют одну общую вершину. Причём если бы мы сжали все циклы в точки, то получится граф без циклов - так называемое "граф-дерево".



Возможно, есть более простое решение, чем то, что я опишу ниже, но я не представляю, как эту задачу можно решать без честного разбора случаев. Моё решение более-менее простое идейно, но весьма сложно в написании (несколько часов написания в лучшем случае).



Давайте теперь учиться решать задачу, т.е. укладывать наш кактус на плоскость.


1) Предположим, что в нашем входном графе нет циклов, т.е. он - дерево.

Тогда укладывать его достаточно просто. Возьмём любую вершину как стартовую, поместим её в точку (0;0). Все вершины, связанные с ней, поместим на второй уровень: с y=1. Дальше, все вершины, связанные с вершинами первого уровня, поместим на второй уровень: y=2. И т.д.

user posted image


2) Предположим теперь, что в графе есть один цикл.

Найдём этот цикл, и выберем любую его вершину как стартовую, поместим её в точку (0;0). Остальные вершины цикла поместим над ней, т.е. на уровень y=1.

user posted image

Мы расположили цикл, теперь займёмся укладкой остального графа. Здесь уже всё становится относительно просто - мы пользуемся той же стратегией, что и в варианте 1), просто подвешивая остатки графа, прицепленные к каждой вершине цикла.

Нам надо только следить за тем, чтобы деревья, привешенные к разным вершинами цикла, не перемешались друг с другом - иначе они начнут пересекаться. В общем, надо поступать как-то так: привесить всё ко второй вершине цикла, найти наибольший получившийся X, и сказать, что к третьей вершине мы будем подвешивать уже начиная с X+1. На рисунке я обвёл эти области оранжевым:

user posted image

Не забыть надо про то, что к стартовой вершине (той, которая в точке (0;0)), может быть также привешено что-то, и это надо будет привесить в последнюю очередь, после того, как мы обработали весь цикл. Опять же, привешиваем мы в такие иксы, чтобы быть гарантированно правее всего, что уже нарисовано. На рисунке я обвёл это фиолетовым:

user posted image


3) Наконец, самый общий случай - т.е. в графе может быть сколько угодно циклов.

К счастью, это не даёт ничего принципиально нового по сравнению с пунктом 2).

Мы берём любой цикл, располагаем его, как описано в пункте 2), затем привешиваем к нему остальные части графа - опять же, как описано в части 2). Если в графе есть где-то другой цикл - ну обработаем его аналогично, т.е. просто поставим его не в (0;0), а в то место, где он окажется.

Короче, говоря умным языком - после того, как мы поставили первый цикл в (0;0), оставшийся граф будем подвешивать рекурсивно.
PM MAIL WWW ICQ   Вверх
  
Ответ в темуСоздание новой темы Создание опроса
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Интересные и занимательные задачи по программированию | Следующая тема »


 




[ Время генерации скрипта: 0.0962 ]   [ Использовано запросов: 22 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.