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

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

HotLog


 

Дорожный аукцион

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

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

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

Исторически сложилось, что право на владение всеми дорогами до недавних пор принадлежали одной известной компании «АвтоДор». В связи с этим в конституционный суд был подан антимонопольный иск, который был удовлетворен – теперь компании предстоит продать часть своих владений. Экономисты компании определили для каждой дороги ее стоимость.

Одна маленькая, небогатая, но гордая фирма «КурсИнвест», в которой Вы работаете финансовым директором, захотела выкупить часть дорог, а именно, K из них. Причем необходимо, чтобы для любых двух городов, к которым примыкает хотя бы одна из выкупленных K дорог, существовало не мене одного соединяющего их пути, состоящего только из приобретенных дорог. Вам, как финансовому директору, было поручено найти экономически выгодное решение. Решение будем называть экономически выгодным, если денежная сумма, потраченная на приобретение дорог, является минимальной.

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

В первой строке входного файла INPUT.TXT находятся три целых числа N (3 ≤ N ≤ 2000), M и К (1 ≤ K < M ≤105), где N – общее количество городов, M – общее количество дорог, K – количество дорог, которое необходимо приобрести.

Далее следует M строк, в каждой из которых записаны три целых числа Ai, Bi и Ci, где Ai и Bi – номера городов, которые соединены дорогой (1 ≤ Ai, Bi ≤ N, Ai ≠ Bi), а Ci – стоимость дороги (1 ≤ Ci ≤ 106). Все числа в строках разделены одиночными пробелами.

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

Выходной файл OUTPUT.TXT должен состоят из K строк, каждая из которых должна содержать одно число – номер приобретенной дороги. Дороги нумеруются в порядке их ввода начиная с единицы. Если решений несколько, то выведите любое из них.

Пример

INPUT.TXTOUTPUT.TXT
19 8 4
8 9 2
5 1 10
3 8 11
2 5 7
8 7 8
5 6 12
4 7 9
3 5 5
4
1
8
3

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

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

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