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

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

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

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

23.05.2014, 00:51. Просмотров 263. Ответов 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.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
23.05.2014, 00:51     Минимальное покрывающее дерево или остов минимального веса
Посмотрите здесь:

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

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

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

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

Максимальное или минимальное значение - C++
Вот я сталкивался с заданием вычесления из массива минимального или максимального значения. Ведь машина понимает что 3>2. Но какое число...

Подскажите как написать такое дерево (или БД) - C++
Задача состоит в том, чтобы построить структуру данных по заданному рекурсивному расписанию каталогов. Причем:Все узлы отсортированны по...

Чем отличается теория графа (дерево или древо) от сети? - C++
Выдали экзамен с такими вопросами, если не сложна напишите ответы я сам себя проверю) 1) Какие структуры элементов позволяют добавить...

Конструктор дерева (не бинарного). Или как вообще правильно строить дерево? - C++
Хочу разобраться с деревьями, да что только не читал, не пересматривал - не могу разобраться. Для примера - хочу построить дерево такого...

Выбрать пару векторов или массивов, которая даст минимальное скалярное произведение - C++
Добрый день, подскажите пожалуйста как создать n векторов или массивов, если изначально не известно сколько их будет? Вот условие...

Определить минимальное или максимальное количество актеров, с которыми режиссер должен переговорить - C++
В театре работает n актеров. Известно, что среди них a – высоких, b – голубоглазых и с – блондинов. Для главной роли в новом спектакле...


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

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

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