SHARE
TWEET

Untitled

a guest May 19th, 2019 118 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. «Безопасные пути»
  2.  
  3. Входной файл: input.txt
  4. Выходной файл: output.txt
  5. Ограничение по времени: 1 секунда
  6. Ограничение по памяти: 64 Mb
  7. Ограничение на размер исходного кода: 50Kb
  8.  
  9. В некотором далёком царстве есть система дорог, представляющая собой неориентированный граф. Каждая дорога соединяет два различных города. Между двумя городами может быть не более одной дороги. Известно, что с течением времени каждая дорога в этом царстве приобрела один из трех статусов. Первый – дороги, на которых регулярно происходят грабежи проезжающих дилижансов (далее – Д1), второй – дороги, на которых стоит царская охрана   (далее – Д2) и третий - статус нейтральной дороги (далее – Д3). Поэтому население данной страны делится на два слоя – добропорядочных  граждан и бандитов. Добропорядочные граждане данной страны ходят только по дорогам Д2 и Д3, а бандиты только по  дорогам Д1 и Д3. Так как царская казна тратит очень много денег на содержание дорог, то царь решил удалить максимальное количество дорог так, чтобы можно было добраться из любого города в любой другой как добропорядочному гражданину, так и грабителю (иначе в стране поднялся бы бунт – могли взбунтоваться как мирные граждане, или бандиты). Ваша задача – найти максимальное количество дорог, которые можно удалить, а также их номера в соответствии с требованиями царя.
  10. Формат входных данных:
  11. В первой строке входного файла input.txt  записано число N — количество городов (1≤N≤1000), а затем число M — количество дорог в царстве (1≤M≤10000). Каждая из последующих   M строк  содержат по три  числа, которые описывают  ровно одну дорогу: первые два  числа задают номера городов, которые она соединяет, а третье — статус дороги: 1 — Д1, 2 — Д2, 3 — Д3. Между любыми двумя городами существует не более одной дороги.
  12. Формат выходных данных:
  13. Первая строка выходного файла output.txt  должна содержать количество удаленных дорог, а во второй строке перечислены их номера, если таковые имеются. Дороги нумеруются в том порядке, в каком они были заданы во входном файле. Если решений несколько, то можно выдать любое из них. Если  решения не существует  выдать: –1.
  14. Пример
  15.  
  16. Input.txt       output.txt              input.txt       output.txt
  17. 5 7             2                       4 5         -1
  18. 1 2 3           4 7                     1 4 2
  19. 2 3 3                                   2 1 1
  20. 3 4 3                                   1 3 3
  21. 5 3 2                                   4 2 1
  22. 5 4 1                                   3 4 3
  23. 5 2 2
  24. 1 5 1
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top