Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Чат
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Новый год

(Время: 1 сек. Память: 16 Мб Сложность: 71%)

Санта Клаус решил сделать новогодний подарок своим эльфам. Конечно же, Санта был бы не Санта, если бы его подарок был обыкновенным. Подарок просто замечательный - эльфы идут в кино!

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

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

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

Помогите Санте, он пока не до конца освоился с компьютером.

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

Первая строка входного файла INPUT.TXT содержит два целых числа n и m - количество мальчиков-эльфов и девочек-эльфов, соответственно (1 ≤ n, m ≤ 100). Вторая строка содержит r – количество пожеланий, которое Санта получил от своих эльфов (1 ≤ r ≤ 1500). Следующие r строк содержат по три целых числа ai, bi и ci каждая. Числа означают, что мальчик-эльф ai хотел бы пойти в кино с девочкой-эльфом bi, и билет на фильм, на который они хотели бы пойти, стоит ci (1 ≤ ci ≤ 1000). Каждый эльф хочет пойти в кино хотя бы с одним другим эльфом.

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

На первой строке выходного файла OUTPUT.TXT выведите минимальную сумму, которую Санте придется потратить, чтобы сделать своим эльфам подарок. На второй строке выведите k - количество билетов, которое Санта должен купить. Наконец, третья строка должна содержать k целых чисел – номера пожеланий, которые следует удовлетворить.

Пример

INPUT.TXTOUTPUT.TXT
13 3
7
1 1 3
1 2 2
1 3 4
2 1 3
2 2 9
3 1 2
3 3 11
11
4
2 3 4 6

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]

Красноярский краевой Дворец пионеров, (c)2006 - 2017, ICQ: 151483