Форум программистов, компьютерный форум CyberForum.ru

Минимальное покрывающее дерево или остов минимального веса - C++

Восстановить пароль Регистрация
 
SerG_doS
0 / 0 / 0
Регистрация: 27.12.2013
Сообщений: 19
23.05.2014, 00:51     Минимальное покрывающее дерево или остов минимального веса #1
Для проведения олимпиады школьников по информатике требуется соединить компьютеры в сеть. Некоторые пары компьютеров должны быть соединены кабелем, и сигнал сможет дойти по кабелям от любого компьютера до любого другого, возможно, через другие компьютеры. Некоторые компьютеры могут быть соединены циклически. Цикл называется простым, если каждый компьютер из этого цикла соединён ровно с двумя другими компьютерами этого цикла, и в этот цикл никакой кабель не входит более одного раза. Некоторые кабели могут не входить ни в какой цикл. Известно, что в разработанной схеме никакой кабель не принадлежит двум простым циклам одновременно. При размещении должны выполняться следующие условия:
1.Компьютеры размещаются на плоскости в точках с целочисленными координатами.
2.Координаты компьютеров x и y лежат в диапазоне 0 ≤ x, y ≤ 100.
3. Никакие два компьютера не располагаются в одной точке.
4. Кабели являются отрезками прямых.
5.Кабели не пересекаются между собой и не проходят через точки размещения компьютеров, к которым они не подключены.
Требуется написать программу, выполняющую размещение компьютеров по заданному описанию схемы.
Входные данные. В первой строке входного файла содержатся числа N и M — количество компьютеров и количество кабелей в схеме (1 ≤ N ≤ 100 000, 0 ≤ M ≤ 200 000). В последующих M строках содержатся пары чисел, разделенных пробелами. Каждая такая пара описывает один кабель, числа представляют собой номера соединенных компьютеров. Компьютеры пронумерованы от 1 до N. Никакая пара не встречается дважды, и никакой кабель не соединяет компьютер с самим собой.
Выходные данные. Выходной файл должен содержать N строк. Строка с номером i должна содержать координаты i-го компьютера x, y. Разрешается вывести любой вариант размещения компьютеров, при котором выполняются условия 1–5.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
23.05.2014, 00:51     Минимальное покрывающее дерево или остов минимального веса
Посмотрите здесь:

C++ Найти минимальное остовное дерево
C++ Максимальное или минимальное значение
C++ Создать программу,которая находит минимальное из 3х чисел. Для нахождения минимального числа создать функцию
C++ Чем отличается теория графа (дерево или древо) от сети?
Подскажите как написать такое дерево (или БД) C++
C++ Определить минимальное или максимальное количество актеров, с которыми режиссер должен переговорить
Построить для заданного графа минимальное основное дерево C++
C++ Выбрать пару векторов или массивов, которая даст минимальное скалярное произведение

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

Текущее время: 17:43. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru