sol
Византийската
империя
отново е
атакувана от
турците. Пратеници
на императора
трябва да посетят
столиците на N съседни
царства, за
да потърсят
помощ. Между
тези градове
има
M двупосочни
пътища, построени
така, че от
всеки град
може да се отиде
до всеки друг
град – пряко
или като се
мине през
други градове. Пътуването
е опасно,
защото има K
банди крадци,
които контролират
пътищата. Всеки
от пътищата
се
контролира
от отделна банда
и за да се
премине
трябва да се
плаща пътна
такса (една и
съща за
всички
пътища). Една
банда може да
контролира много
пътища, но разрешава
минаването по
най-много един
от тях. Разбира
се,
пратениците
на
императора
не искат да
плащат
излишно на
бандитите. Ако
за някакъв
път таксата е
платена, по
него може да
се преминава
свободно
произволен
брой пъти във
всяка посока.
Всички
пратеници
тръгват от
град 1.
Задача
Напишете програма, която пресмята минималния брой пътища, за които трябва да се плати пътна такса, така че всеки град да бъде достижим от град 1, като се минава само по пътища, за които е платено и никоя банда да не контролира повече от един от избраните пътища.
Входи
Входният
файл sol.in има
следната
структура:
- ред 1 съдържа
три цели
положителни
числа, разделени
с по един интервал,
N M K, представляващи,
съответно,
броя на
градовете,
броя на
пътищата и броя
на бандите
крадци;
- редове 2, . . . , M+1 съдържат
по две цели
положителни
числа,
разделени с
интервал, x
y (1<=x,y<=N), което
означава, че
има път между
град x и град y;
- редовете M+2, . . . , M+K+1 съдържат
едно цяло число
pi (0<pi<=M), следвано
от pi цели числа
x1,
x2,
?, xpi(0<xj<=M, 0<j<=pi), задаващи
броя на пътищата
контролирани
от i-тата
банда, както
и номерата на
пътищата,
които тя
контролира.
Всички числа
са разделени
с по един
интервал. Описанието
за банда i се намира на
ред M+i+1. Пътищата
са
номерирани с
числата от 1 до M според
реда им във
входния файл.
Всеки път се
появява
точно веднъж
на някой от редовете
M+2, . . . , M+K+1.
Изход
Първият
ред на
изходния
файл sol.out трябва
да съдържа
цяло
положително
число D, представляващо
броя на
избраните
пътища или -1, ако не
съществува
решение. Ако
има решение,
следващият
ред трябва да
съдържа D цели
числа
разделени с
по един
интервал, представляващи
избраните
пътища. Редовете
са
номерирани с
числата от 1 до M,
според
появяването
им във
входния файл.
Редът на
извеждане на
избраните
пътища е без
значение. Ако
има няколко
различни решения,
всяко едно от
тях ще се
приема за
вярно.
Ограничения
Пример
sol.in |
sol.out |
6
9 5 |
5 |
Ограничение
за време: 0.1
секунди на
тест
student Codrut Grosu
Automatics and Computer Department, Polytechnic
University of Bucharest
grosu_codrut@yahoo.com
Превод
на български:
Стоян Капралов