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

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

Восстановить пароль Регистрация
 
AC-93
13 / 13 / 0
Регистрация: 27.01.2010
Сообщений: 150
16.04.2012, 14:55     Гамильтонов цикл в графе с выполненным условием Дирака #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++
Найти цикл в графе C++
C++ Цикл ввода с условием
While-цикл с условием. C++
C++ Графы. Гамильтонов Цикл. Матрица смежности
C++ Вывод на экран двусвязного списка, цикл с условием

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
mano
0 / 0 / 0
Регистрация: 11.04.2013
Сообщений: 42
28.01.2015, 19:18     Гамильтонов цикл в графе с выполненным условием Дирака #2
Здравствуйте. Решаю ту же задачу. Вы случайно не помните, как она решалась?
Yandex
Объявления
28.01.2015, 19:18     Гамильтонов цикл в графе с выполненным условием Дирака
Ответ Создать тему
Опции темы

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