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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Подскажите как исправить функцию http://www.cyberforum.ru/cpp-beginners/thread919955.html
bool addNode(TNode *first, int key) { TNode* tmp=first; if(tmp->Right) addNode(tmp->Right,key); else if(tmp->Data==-1||tmp->Data==-2||tmp->Data==-3) { tmp->Right=add(key);...
C++ Ошибка в инициализации базовых классов Привет. Пишу код из книги Лафоре. #include <iostream> using namespace std; #include <windows.h> enum posneg {pos, meg}; class Distance { protected: int feet; http://www.cyberforum.ru/cpp-beginners/thread919943.html
C++ Как правильно описать функцию acos?
И ребят помогите разобраться в чем ошибки здесь, делаю лабораторную по методу секущих И еще как можно графически выполнить метод секущих через Dos Box? Заранее благодарю за помощь #include...
Сортировка массива по убыванию элементов C++
Скажите пожалуйста, что не так, если не так, в этом коде) Задание: отсортировать массив по убыванию значений элементов в строках и столбцах методом пузырька #include <iostream> #include <conio.h>...
C++ Указание ключа компилятора для OpenMP http://www.cyberforum.ru/cpp-beginners/thread919923.html
смотрю на сайте http://edu.chpc.ru/parallel/mainse4.html Для использования механизмов OpenMP нужно скомпилировать программу компилятором, поддерживающим OpenMP, с указанием соответствующего ключа...
C++ Работа с файлами (запись данных, сортировка) Здравствуйте, помогите пожалуйста с заданием: написать программу, которая запрашивает у пользователя имя, фамилию, дату рождения, номер группы, пол, рост, вес и записывает данные в файл. Программа... подробнее

Показать сообщение отдельно
Denisqwwq
38 / 32 / 1
Регистрация: 01.06.2013
Сообщений: 117

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

08.07.2013, 23:51. Просмотров 915. Ответов 10
Метки (Все метки)

Вот наткнулся сегодня на такую задачу:
Всем известно, что в позапрошлом веке ковбои занимались перегоном скота. Перегон скота всегда считался опасным делом. Ковбой Джон, готовясь к очередному перегону, изучал план местности. Так как местность гористая, то добраться из одного поселения в другое можно только по дорогам, возможно через другие поселения. Главной опасностью на пути были бандиты, проживающие в разных населенных пунктах, и организующие группировки для нападения на ковбоев. Чтобы их разобщить, Джон разработал гениальный план полной изоляции поселений друг от друга.

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

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

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

В первой строке входного файла 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. Готовое решение не предлагать, лучше совет по реализации
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru