Главное меню портала
• О портале
• Архив задач
• Карта архива задач
• Результаты тестов
• Ошибки тестирования
• Преподаватели
• Библиотечка
Рейтинг у учителя
• Рейтинг на портале
Начинающему
• Работа с порталом
• Курс для начинающего
• Архив задач начинающего
Олимпиаднику
• Архив задач олимпиадника
Олимпиады
Дистанционные олимпиады
• Положение олимпиады
Новое сообщениеОтправленые
Загрузка...
Время на прохождение теста: 1 секунд(а/ы).
Имя входного файла: input.txt
Имя выходного файла: output.txt

Автор: Бельский Андрей Владимирович

Безопасные пути

Ограничение по времени: 1 секунда

Ограничение по памяти: 64 Mb

В некотором далёком царстве есть система дорог, представляющая собой неориентированный граф. Каждая дорога соединяет два различных города. Между двумя городами может быть не более одной дороги. Известно, что с течением времени каждая дорога в этом царстве приобрела один из трех статусов. Первый – дороги, на которых регулярно происходят грабежи проезжающих дилижансов (далее – Д1), второй – дороги, на которых стоит царская охрана   (далее – Д2) и третий - статус нейтральной дороги (далее – Д3). Поэтому население данной страны делится на два слоя – добропорядочных  граждан и бандитов. Добропорядочные граждане данной страны ходят только по дорогам Д2 и Д3, а бандиты только по  дорогам Д1 и Д3. Так как царская казна тратит очень много денег на содержание дорог, то царь решил удалить максимальное количество дорог так, чтобы можно было добраться из любого города в любой другой как добропорядочному гражданину, так и грабителю (иначе в стране поднялся бы бунт – могли взбунтоваться как мирные граждане, или бандиты). Ваша задача – найти максимальное количество дорог, которые можно удалить. 

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

В первой строке входного файла input.txt  записано число N — количество городов (1<=N<=1000), а затем число M — количество дорог в царстве (1<=M<=10000). Каждая из последующих   M строк  содержат по три  числа, которые описывают  ровно одну дорогу: первые два  числа задают номера городов, которые она соединяет, а третье — статус дороги: 1 — Д1, 2 — Д2, 3 — Д3. Между любыми двумя городами существует не более одной дороги.

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

Первая строка выходного файла output.txt  должна содержать количество удаленных дорог. Если решений несколько, то можно выдать любое из них. Если  решения не существует  выдать: –1.


Примеры:
input.txt output.txt
1 5 7
1 2 3
2 3 3
3 4 3
5 3 2
5 4 1
5 2 2
1 5 1
2
2 4 5
1 4 2
2 1 1
1 3 3
4 2 1
3 4 3
-1

Сложность задачи: 50%



Проверку могут осуществлять только зарегистрированные пользователи!


Разбор задачи

Решение задачи разобьём на три этапа.

Первый этап – найдём все деревья состоящие из дорог типа Д3, пронумеруем их – a1ak. По этим дорогам можно ездить всем.

Второй этап – из этих деревьев a1ak составим граф, в котором ai и aj соединены дорогой Д1 или(и) Д2, если в исходном графе эта же дорога(дороги) соединяла(соединяли) вершины из ai и aj.

Третий этап – построим лес поиска в глубину по дорогам типа Д1. Если этот лес Л1 состоит не из одного дерева(т.е. мы не можем проехать из любого города в любой по дорогам типа Д1 и Д3), то решения задачи не существует, выводим -1. Затем построим лес поиска в глубину по дорогам типа Д2. Если этот лес Л2 состоит не из одного дерева, то также решения не существует, выводим -1. Если условия не нарушены, то в исходном графе останутся дороги принадлежащие a1ak , Л1 и Л2, все остальные дороги следует выдать в выходной файл.

Показать обсуждение


На сайте гостей 21, зарегистрированных 0:
Сейчас онлайн только гости...
[Данные за последние 5 минут]