Рубрики

Опыт национальных инструментов интервью | Набор 2

Межпланетная торговля:
Хобер Мэллов хочет установить межгалактическую торговлю, которая позволила бы торговать между различными планетами. У каждой планеты есть свой набор валют, в которых они торгуют. Поскольку валют слишком много, Хобер решил объявить набор из M валют (пронумерованных от 1 до M) в качестве официальных валют, которые можно использовать для торговли между планетами. Две планеты могут торговать тогда и только тогда, когда они имеют общую официальную валюту или если есть другая планета, с которой каждая из этих планет имеет общую официальную валюту. Например, предположим, что у планеты А есть валюты — 1, 3, 4, у планеты В — валюты 5, 6, а у планеты С — 6, 4. Планета А и В все еще могут торговать через планету С (планета А -> C через валюту 4, а затем планету C -> B через валюту 6 и наоборот). Этот тип торговли может быть осуществлен с более чем одной планетой, выступающей также в качестве посредника (т.е. планеты X и Y могут торговать через A, B, C, если XA делят общую валюту, AB делят общую валюту, BC делят общую валюту и наконец CY делят некоторую общую валюту). Хобер отмечает, что даже с этими правилами есть планеты, у которых нет официальных валют или групп планет, которые не делят валюту с другими группами планет. Чтобы обеспечить торговлю между всеми планетами, он должен внедрить систему новой валюты для каждой из таких планет, которые не имеют официальных или общих официальных валют. Внедрение новой валютной системы обходится ему в 1 платиновую единицу за планету. Вы должны помочь Хоберу минимизировать стоимость, позволяющую торговать между всеми планетами.

Вам будет дано N (2 <= N <= 50), которое указывает количество планет, которые хотят участвовать в межгалактической торговле. Вам будет дано значение M (2 <= M <= 50), которое указывает номер официальной валюты, пронумерованный от 1 до M. За ним последуют N строк, каждая из которых состоит из числа Ci, количества официальных валют, поддерживаемых планетой i Далее следуют валюты C, которые обменивают на i-ю планету. Вы должны вывести количество платиновых единиц, необходимое для включения торговли на всех планетах.

Пример входов

5 5
1 2
2 2 3
2 3 4
2 4 5
1 5

5 5
0
3 4 1 5
2 3 4
0
1 2
Ожидаемые результаты

0
Планеты № 1 и № 2 могут торговать через валюту 2. Планеты № 2 и № 3 могут торговать через валюту 3. Планеты № 3 и № 4 могут торговать с использованием 4. Планеты № 4 и № 5 могут торговать с использованием валюты 5. Это делает его можно торговать между любыми двумя планетами через ноль или более промежуточных планет. Таким образом, нет необходимости устанавливать новую валюту и, следовательно, стоимость равна 0.
3
Планеты № 2 и № 3 могут торговать через валюту 4, но планеты № 1, № 4 и № 5 не делят какую-либо валюту друг с другом или с № 2 и № 3 и, следовательно, не могут торговать с кем-либо еще. Одна из валют с планет № 2 или № 3 может быть установлена на планетах № 1, № 4 и № 5, что сделало бы торговлю возможной между всеми планетами. Поскольку валюта должна быть настроена на 3 разных планетах, стоимость составляет 3.

Пример входов и выходов
Тестовый ввод-вывод Скачать Link Run Link (также сохраняет код)
1
5 5
1 2
2 2 3
2 3 4
2 4 5
1 5
0
Скачать входной файл Запуск против кода
2
5 5
0
3 4 1 5
2 3 4
0
1 2
3
Скачать входной файл Запуск против кода
Ограничение по времени на тестовый случай:

2 секунды

Если у вас есть машина с GCC / G ++ и вы хотите работать в автономном режиме, загрузите шаблон здесь и отправьте

Шаблоны кода:

C Шаблон: Trade.c

Шаблон C ++: Trade.cpp

Эта статья предоставлена Бхаратом. Если вам нравится GeeksforGeeks и вы хотите внести свой вклад, вы также можете написать статью и отправить ее по почте на contrib@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Напишите свой опыт интервью или отправьте его по электронной почте на адрес contrib@geeksforgeeks.org

Рекомендуемые посты:

Опыт национальных инструментов интервью | Набор 2

0.00 (0%) 0 votes