| Автор: | std.alg | Ограничение времени: | 2 сек | |
| Входной файл: | minimal.in | Ограничение памяти: | 256 Мб | |
| Выходной файл: | minimal.out |
Требуется построить в двудольном графе минимальное контролирующее множество, если дано максимальное паросочетание.
В первой строке файла даны два числа m и n (1 ≤ m, n ≤ 4 000) — размеры долей. Каждая из следующих m строк содержит список ребер, выходящих из соответствующей вершины первой доли. Этот список начинается с числа Ki (0 ≤ Ki ≤ n) — количества ребер, после которого записаны вершины второй доли, соединенные с данной вершиной первой доли, в произвольном порядке. Сумма всех Ki во входном файле не превосходит 500 000.
Последняя строка файла содержит некоторое максимальное паросочетание в этом графе — m чисел 0 ≤ Li ≤ n — соответствующая i-й вершине первой доли вершина второй доли, или 0, если i-я вершина первой доли не входит в паросочетание.
Первая строка содержит размер минимального контролирующего множества.
Вторая строка содержит количество вершин первой доли S, после которого записаны S чисел — номера вершин первой доли, входящих в контролирующее множество, в возрастающем порядке.
Третья строка содержит описание вершин второй доли в аналогичном формате.
| № | Входной файл (minimal.in) |
Выходной файл (minimal.out) |
|---|---|---|
| 1 | |
|