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

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

Войти
Регистрация
Восстановить пароль
 
AC-93
16 / 16 / 0
Регистрация: 27.01.2010
Сообщений: 150
#1

Гамильтонов цикл в графе с выполненным условием Дирака - C++

16.04.2012, 14:55. Просмотров 752. Ответов 1
Метки нет (Все метки)

Задача
:Задача 1 . SMS счастья
Имя входного файла: input.txt
Имя выходного файла: output.txt
Ограничение по времени: 2 секунды на тест
Ограничение по памяти: 64 Мб
Студенты факультета информационных технологий Урюпинского государственного
университета разрабатывают систему оповещения о различных событиях, таких, например, как
назначение даты экзамена. В качестве транспортной среды для этой системы оповещения были
выбраны SMS. Все студенты курса имеют сотовые телефоны, которые постоянно включены.
Каждый студент в своей адресной книге помимо других записей имеет номера, по крайней мере,
половины своих однокурсников. А те однокурсники, которые записаны в его адресной книге,
имеют его номер тоже.
Всем понятно, что несправедливо заставлять инициатора рассылки сообщения платить за
отправку SMS всем остальным студентам курса, поэтому было решено отправлять SMS по кругу:
каждый получатель сообщения отправляет его следующему студенту. Последний студент в
цепочке должен переслать SMS инициатору рассылки. Этим достигаются два полезных
результата. Во-первых, инициатор рассылки таким образом узнает, дошло ли его сообщение до
всех студентов. Во-вторых, благодаря этому любой студент может выступать в роли инициатора
рассылки.
Вам передано содержимое адресных книг телефонов всех студентов курса. Вам необходимо
написать программу, которая строит возможный маршрут рассылки сообщений,
удовлетворяющий следующим требованиям:
1. Маршрут должен быть замкнутым
2. Маршрут должен проходить через телефон каждого из студентов ровно один раз.
3. Следующим звеном в маршруте всегда должен быть телефон, записанный в адресной книге
текущего телефона.
Входные данные
В первой строке входного файла задано количество студентов на курсе N (2<N≤300).
В следующих N блоках задается информация о содержимом адресной книги каждого из
студентов курса. В первой строке i-го блока записаны фамилия i-го студента и через пробел
целое число — количество записей в адресной книге его телефона ((N+1)/2≤ Ki
≤ 100, 1 ≤ i ≤ N).
В следующих Ki
строках перечислены записи его адресной книги. Заданы только фамилии, по
одной в строке. Все фамилии имеют длину не более 16 символов латиницы, большие и
маленькие буквы не различаются.
Нужно иметь в виду, что в адресных книгах могут встречаться телефоны людей, не являющихся
студентами этого курса.
Выходные данные
В выходной файл необходимо вывести один из возможных маршрутов рассылки,
удовлетворяющий указанным в условии задачи требованиям. Маршрут выводится в виде списка
N фамилий, по одной фамилии в строке.
Пример
input.txt output.txt
4
Ivanov 3
Petrov
Sidorov
Pentyushkin
Petrov 2
Sidorov
Ivanov
Ivanov
Petrov
Sidorov
Pentyushkin

Sidorov 3
Pentyushkin
Ivanov
Petrov
Pentyushkin 3
Ivanov
Kuznetsov
Sidorov

В начале прочитали, мапом отсеяли лишние, пронумеровали, храним в матрице доступности возможность звонка.
а как потом их садить? вроде находил алгоритм пару недель назад, но сейчас не могу найти(
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
16.04.2012, 14:55
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Гамильтонов цикл в графе с выполненным условием Дирака (C++):

Гамильтонов цикл в графе - C++
Нужно написать функцию нахождения гамильтонова цикла в графе. Цикл ищется по матрице смежности которая вводится с клавиатуры. Собственно...

Гамильтонов цикл - C++
надо разобрать прогу.выявления Гамильтонова цикла в графе...

Гамильтонов Цикл (из Delphi в C++) - C++
Здравствуйте дорогие форумчане! Прошу прощение за беспокойство.Сразу к сути. Мне необходимо переписать данный алгоритм из книги на языке...

Графы. Гамильтонов Цикл. Матрица смежности - C++
Вот программа, которую я взял с поиска. Программа должна найти Гамильтонов цикл. #include &lt;iostream.h&gt; #include &lt;stdlib.h&gt; const...

Цикл с параметром и цикл с условием - C++
1. Составить программу вычисления суммы первых 10 непарных чисел 2. Дано числовой ряд и некоторое число &quot;епсила&quot;. Найти сумму...

Найти цикл в графе - C++
Дан граф, содержащий только один цикл. Нужно найти его (все его вершины). Код не нужен, нужна только идея.

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
mano
0 / 0 / 0
Регистрация: 11.04.2013
Сообщений: 43
28.01.2015, 19:18 #2
Здравствуйте. Решаю ту же задачу. Вы случайно не помните, как она решалась?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.01.2015, 19:18
Привет! Вот еще темы с ответами:

While-цикл с условием. - C++
Дано целое число N(&gt;0). Если оно является степенью числа 3, то вывести TRUE, если не является-вывести FALSE. #include &lt;stdio.h&gt; ...

цикл с условием - C++
дано число N (&gt;1). Вывести наиболее из целых чисел к, ДЛЯ КОТОРЫХ СУММА 1+1/2+...+1/К будет больше А, и саму эту сумму.

Цикл ввода с условием - C++
Добрый вечер. У меня есть вопрос касательно кода. Как его зациклить? Я имею ввиду, чтобы на шаге &quot;Oshibka&quot; возвращало снова к вводу. Также...

Вернуть рёбра из которых состоит цикл в графе - C++
допустим, есть граф, как на картинке. визуально и так видно, что там циклы, это: 1 2 3 4 5 и 6 7 8, но как реализовать, чтобы...


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

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

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