Электрические провода
Электрические провода
Имеется электрическая цепь дома с заданным количеством узлов, некоторые из которых связаны проводами. Любая пара узлов может быть соединена максимум одним проводом. Никакой узел не может быть подключен сам к себе. Каждый узел цепи является либо домашней электрической розеткой, либо подключен к основной внешней электросети.
Вы хотите сделать схему безопасной и избыточной, добавив столько дополнительных проводов, на сколько это возможно. Единственная сложность заключается в том, что никакие два внешних узла электросети на данный момент не соединены между собой (прямо или косвенно), и Вам следует сохранить это свойство, иначе произойдет замыкание. Найдите максимальное количество новых проводов, которое можно добавить в схему.
Входные данные
Состоит из нескольких тестов. Первая строка каждого теста содержит количество узлов схемы n (1 ≤ n ≤ 50), пронумерованных целыми числами от 0 до n - 1. Следующие n строк описывают имеющиеся в наличии провода: x-ый символ строки y равен 1 (единица), если вершины x и y соединены проводом, и 0 (ноль) иначе. Следующая строка содержит количество узлов, подсоединенных к основной электросети, за которой следует список самих узлов.
Выходные данные
Для каждого теста вывести в отдельной строке максимальное количество новых проводов, которое можно добавить в электрическую схему.
3 000 000 000 2 0 1 5 01000 10100 01010 00100 00000 2 2 4
1 3