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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
SerG_doS
0 / 0 / 0
Регистрация: 27.12.2013
Сообщений: 19
#1

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

23.05.2014, 00:51. Просмотров 275. Ответов 0
Метки нет (Все метки)

Для проведения олимпиады школьников по информатике требуется соединить компьютеры в сеть. Некоторые пары компьютеров должны быть соединены кабелем, и сигнал сможет дойти по кабелям от любого компьютера до любого другого, возможно, через другие компьютеры. Некоторые компьютеры могут быть соединены циклически. Цикл называется простым, если каждый компьютер из этого цикла соединён ровно с двумя другими компьютерами этого цикла, и в этот цикл никакой кабель не входит более одного раза. Некоторые кабели могут не входить ни в какой цикл. Известно, что в разработанной схеме никакой кабель не принадлежит двум простым циклам одновременно. При размещении должны выполняться следующие условия:
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.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
23.05.2014, 00:51
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Минимальное покрывающее дерево или остов минимального веса (C++):

Найти минимальное остовное дерево - C++
Дан полный взвешенный граф, кол-во вершин задается пользователем, вес ребер рандомный от 1 до 100. Найти минимальное остовное дерево при...

Алгоритм Прима. Минимальное островное дерево - C++
Всем доброго времени суток. Сейчас нахожусь в полной фрустрации, т.к уже пару часов не могу найти исходник алгоритма Прима на С++. Сам...

Построить для заданного графа минимальное основное дерево - C++
Построить для заданного графа минимальное основное дерево. Помогите на С++ написать задачку) Найти минимальный путь.

Используя очередь или стек, описать процедуру или функцию, определяющую число вхождений элемента Е в дерево Т - C++
Народ помогите пожалуйста! Проблема в том, что не понимаю суть задания. Прошу не код, а объяснения принципа реализации. С чего начать? как...

Создать программу,которая находит минимальное из 3х чисел. Для нахождения минимального числа создать функцию - C++
Создать функцию - double mini (double a, double b, double c), где a,b,c - задание числа. Спасибо за помощь!

Минимальный остов (каркас, остовное дерево) - Алгоритмы
Написал прогу вычисляющую длину минимального остовного дерева по алгоритму Прима, успешно сдал на школе программиста...

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.05.2014, 00:51
Привет! Вот еще темы с ответами:

Постройте каркас минимального веса для графа заданного матрицей весов - Дискретная математика
Постройте каркас минимального веса для графа заданного матрицей весов(2 балла) помогите срочно плиз

Получить сведения о багаже минимального веса, в котором более двух вещей - Delphi
Получить сведения о багаже минимального веса, в котором более двух вещей.

Найти его основное дерево наименьшего веса; изобразить его графически с необходимыми комментариями. - Дискретная математика
Дана матрица весов ребер полного 7 –вершинного неориентированного графа. Найти его основное дерево наименьшего веса; изобразить его...

Минимальное остовное дерево PASCAL - Pascal
Написал программу для нахождения минимального остовного дерева, но вместо вывода номеров тех городов, которые он посетил, выводит нули....


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

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru