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

Олимпиадная задача - C++

Восстановить пароль Регистрация
 
Denisqwwq
 Аватар для Denisqwwq
38 / 32 / 1
Регистрация: 01.06.2013
Сообщений: 117
08.07.2013, 23:51     Олимпиадная задача #1
Вот наткнулся сегодня на такую задачу:
Всем известно, что в позапрошлом веке ковбои занимались перегоном скота. Перегон скота всегда считался опасным делом. Ковбой Джон, готовясь к очередному перегону, изучал план местности. Так как местность гористая, то добраться из одного поселения в другое можно только по дорогам, возможно через другие поселения. Главной опасностью на пути были бандиты, проживающие в разных населенных пунктах, и организующие группировки для нападения на ковбоев. Чтобы их разобщить, Джон разработал гениальный план полной изоляции поселений друг от друга.

Посоветовавшись с напарниками, Джон пришел к выводу, что временно дороги можно вывести из строя, устроив камнепад. Под покровом ночи можно выехать из одного населения в другое, остановиться где-то посреди дороги и устроить камнепад так, чтобы по этой дороге нельзя больше проехать никому. Камни падают позади повозки, поэтому обратной дороги нет. Но зато можно ехать в другой населенный пункт, и если из него существуют дороги, то и их можно вывести из строя.

Сам Джон этого сделать не может, только он знает тайные тропы и должен перегонять стадо. Поэтому он решил использовать наемников. Наемники есть в любом поселении и в любом количестве, однако, за каждого из них приходится платить не малую сумму, поэтому Джон хочет потратить как можно меньше денег. Помогите Джону определить минимальное число наемников, которые смогут привести в непригодность абсолютно все дороги и изолировать все поселения.

Входные данные

В первой строке входного файла INPUT.TXT находятся два целых неотрицательных числа N (0 < N < 1000) – количество поселений и M (0 <= M <= 100 000) – количество дорог, их соединяющих. Далее следует M строк, содержащих описание дорог. В i-й строке находятся два натуральных числа V и U (1 <= V, U <= N) – номера поселений, которые соединяет i-я дорога. Между двумя различными поселениями существует не более одной дороги, но может существовать несколько маршрутов. Нет дорог, которые образуют петлю, исходящую из поселения и ведущую в него же, не заходя в другие поселения. Не гарантируется, что существует маршрут между любой парой поселений. Маршрутом называется такая последовательность поселений s1-s2- … -sn, что любые два последовательных поселения si и si+1 соединены дорогой.

Выходные данные

В выходной файл OUTPUT.TXT выведите минимальное количество наемников, необходимое для изоляции всех поселений.


Никак не могу реализовать её.
Есть у кого-нибудь идеи ?
P.S. Готовое решение не предлагать, лучше совет по реализации
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.07.2013, 23:51     Олимпиадная задача
Посмотрите здесь:

C++ Олимпиадная задача на числа
Олимпиадная задача C++
C++ Олимпиадная задача
Олимпиадная задача C++
Задача на дп (олимпиадная) C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Мимино
 Аватар для Мимино
180 / 151 / 5
Регистрация: 22.05.2013
Сообщений: 435
Записей в блоге: 1
09.07.2013, 00:46     Олимпиадная задача #2
Задачей коммивояжера попахивает. Пробовали?

Добавлено через 7 минут
Мне кажется, что решение кроется в применении правильного алгоритма для обхода графа/дерева. Какой подход выбрали Вы?
Radagast
4 / 0 / 1
Регистрация: 09.07.2013
Сообщений: 17
09.07.2013, 03:03     Олимпиадная задача #3
Первым делом надо определить количество компонент связности графа.
Далее считаем, что есть только одна компонента связности, т.е. граф связный.
Выделяем максимальный подграф, содержащий полный эйлеров цикл (т.е. такой, в котором можно пройти по всем ребрам по одному разу и вернуться в исходную точку - критерий "эйлеровости" графа очень прост: степени всех вершин должны быть четными). Удаляем этот цикл из графа, прибавляем одного наемника к минимальному числу. Остается несколько новых компонент связности. Та, которая соединяется с удаленным эйлеровым подграфом исходной (последней) точкой, априори нового наемника не требует (но не обязательно не требует), на остальные нужно еще как минимум по одному. Работаем с ними точно так же, выделяя максимальный эйлеров подграф, далее прибавляем наемников, учитывая предыдущее предложение. По-моему, так будет правильно.

Добавлено через 22 минуты
Пардон, не дописал: в конце концов останутся только графы без циклов. Ну тут все просто - связный граф без циклов - это дерево. Сколько листьев - столько и наемников.
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
09.07.2013, 09:31     Олимпиадная задача #4
на мой взгляд, достаточно посчитать количество компонент связности.

Добавлено через 16 минут
я оказался неправ...)
vndtta
66 / 43 / 5
Регистрация: 17.10.2011
Сообщений: 146
Завершенные тесты: 1
09.07.2013, 09:47     Олимпиадная задача #5
для начала нужно составить карту графа NxN
потом посчитать степень каждой вершины

затем находим вершину с ниаменьшей степенью (кроме 0)
запоминаем ее степень как максимум
уменьшаем степень всех инцидентных вершин на 1
степень самой вершины устанавливаем в 0
из карты удаляем все ребра исходящие из этой вершины
снова ищем вершину с ниаменьшей степенью (кроме 0) ... и т.д.

итак наш максимум и есть минимальное количество наемников
Radagast
4 / 0 / 1
Регистрация: 09.07.2013
Сообщений: 17
09.07.2013, 10:11     Олимпиадная задача #6
vndtta,
Опишите, если нетрудно, пошагово, как вашим алгоритмом посчитать минимальное количество наемников для обхода треугольника? Вроде как получается так: находим любую вершину, ее степень - 2. Запоминаем 2 как максимум. Удаляем инцидентные ребра, получаем отрезок. Находим вершину со степенью 1. 1 < 2, поэтому максимум не меняется. Удаляем ребро, получаем пустой граф. Запомненный максимум - 2, хотя, очевидно, достаточно всего одного наемника.
Или я неправильно понял алгоритм?
vndtta
66 / 43 / 5
Регистрация: 17.10.2011
Сообщений: 146
Завершенные тесты: 1
09.07.2013, 10:12     Олимпиадная задача #7
Цитата Сообщение от Radagast Посмотреть сообщение
vndtta,
Опишите, если нетрудно, пошагово, как вашим алгоритмом посчитать минимальное количество наемников для обхода треугольника? Вроде как получается так: находим любую вершину, ее степень - 2. Запоминаем 2 как максимум. Удаляем инцидентные ребра, получаем отрезок. Находим вершину со степенью 1. 1 < 2, поэтому максимум не меняется. Удаляем ребро, получаем пустой граф. Запомненный максимум - 2, хотя, очевидно, достаточно всего одного наемника.
Или я неправильно понял алгоритм?
начиная с любой вершины нужно изолировать ее - т.е. засыпать камнями 2 дороги - 2 наемника
Radagast
4 / 0 / 1
Регистрация: 09.07.2013
Сообщений: 17
09.07.2013, 10:20     Олимпиадная задача #8
vndtta, но, судя по этому абзацу,
Цитата Сообщение от Denisqwwq Посмотреть сообщение
Посоветовавшись с напарниками, Джон пришел к выводу, что временно дороги можно вывести из строя, устроив камнепад. Под покровом ночи можно выехать из одного населения в другое, остановиться где-то посреди дороги и устроить камнепад так, чтобы по этой дороге нельзя больше проехать никому. Камни падают позади повозки, поэтому обратной дороги нет. Но зато можно ехать в другой населенный пункт, и если из него существуют дороги, то и их можно вывести из строя.
можно и не изолировать сразу вершину - достаточно пройтись по кругу, засыпая за собой дорогу камнями, и вернуться в исходную точку - при этом все поселений станут изолированными, но понадобится всего один наемник.
vndtta
66 / 43 / 5
Регистрация: 17.10.2011
Сообщений: 146
Завершенные тесты: 1
09.07.2013, 10:33     Олимпиадная задача #9
Цитата Сообщение от Radagast Посмотреть сообщение
vndtta, но, судя по этому абзацу,

можно и не изолировать сразу вершину - достаточно пройтись по кругу, засыпая за собой дорогу камнями, и вернуться в исходную точку - при этом все поселений станут изолированными, но понадобится всего один наемник.
так джон по дорогам должен ходить? а зачем ему знать секретные тропы тогда?
что делать если граф получится не однодольный или в нем больше 2 вершин с нечетной степенью?
Radagast
4 / 0 / 1
Регистрация: 09.07.2013
Сообщений: 17
09.07.2013, 10:43     Олимпиадная задача #10
Например, такой?
Действуем, как я описал выше - находим эйлеров граф в центре, убираем его, остается две компоненты связности, одна из которых была инцидентна вершине эйлерова подграфа, из которой можно начать и в которой можно закончить его обход. Таким образом, нужно ровно два наемника.
Изображения
 
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.07.2013, 11:12     Олимпиадная задача
Еще ссылки по теме:

Олимпиадная задача. Деревни C++
C++ C++. Олимпиадная задача
Сладкая олимпиадная задача C++

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

Или воспользуйтесь поиском по форуму:
vndtta
66 / 43 / 5
Регистрация: 17.10.2011
Сообщений: 146
Завершенные тесты: 1
09.07.2013, 11:12     Олимпиадная задача #11
Цитата Сообщение от Radagast Посмотреть сообщение
Например, такой?
Действуем, как я описал выше - находим эйлеров граф в центре, убираем его, остается две компоненты связности, одна из которых была инцидентна вершине эйлерова подграфа, из которой можно начать и в которой можно закончить его обход. Таким образом, нужно ровно два наемника.
так то да, но это простой вариант
до меня вобщем доперло

нужно граф разделить на не связные друг с другом однодольные подграфы {Gi}
для каждого подграфа Gi посчитать количество вершин с нечетной степенью ki, тогда количество наемников дял подграфа - mi[(k+1)/2]( чтобы пройти по каждому ребру 1 раз)
итог сумма mi

Добавлено через 20 минут
забыл добавить что mi не меньше 1
Yandex
Объявления
09.07.2013, 11:12     Олимпиадная задача
Ответ Создать тему
Опции темы

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