2383. Электрические провода

Имеется электрическая цепь дома с заданным количеством узлов, некоторые из которых связаны проводами. Любая пара узлов может быть соединена максимум одним проводом. Никакой узел не может быть подключен сам к себе. Каждый узел цепи является либо домашней электрической розеткой, либо подключен к основной внешней электросети.

Вы хотите сделать схему безопасной и избыточной, добавив столько дополнительных проводов, на сколько это возможно. Единственная сложность заключается в том, что никакие два внешних узла электросети на данный момент не соединены между собой (прямо или косвенно), и Вам следует сохранить это свойство, иначе произойдет замыкание. Найдите максимальное количество новых проводов, которое можно добавить в схему.

Вход. Состоит из нескольких тестов. Первая строка каждого теста содержит количество узлов схемы 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

РЕШЕНИЕ

графы – поиск в глубину

Анализ алгоритма

Построим матрицу смежности графа m. Подсчитаем в переменной Edges общее количество имеющихся проводов (ребер графа): для этого следует подсчитать общее число единиц в массиве m и поделить его на 2 (каждое ребро будет подсчитано дважды, так как имеющийся граф является неориентированным).

Каждая вершина, подключенная к наружной сети, вместе с вершинами, связанными с ней (даже не напрямую), образуют отдельную компоненту связности. При помощи поиска в глубину выделим эти компоненты. Очевидно, что граф распадется на множество компонент, каждая из которых содержит одну вершину, подключенную к наружной сети. При этом останется некоторое множество вершин, не входящее ни в одну из компонент. Пусть последнее множество содержит LeftVertex вершин. Между вершинами, входящими в разные компоненты связности, провода протягивать нельзя, так как произойдет замыкание. Между двумя вершинами, входящими в одну компоненту, можно добавить провод, если только он не был между ними изначально. Между любыми двумя из оставшихся LeftVertex вершин можно добавить провод. Для максимизации общего числа проводов множество из LeftVertex вершин необходимо присоединить к той компоненте связности, которая имеет наибольшее число вершин. В переменной MaxConnComp будем вычислять величину наибольшей компоненты связности. При помощи глобальной переменной Vertex в функции dfs будем подсчитывать число вершин, входящих в текущую компоненту связности. Если текущая компонента связности содержит Vertex вершин, то максимум она может содержать Vertex * (Vertex – 1) / 2 ребер (полный граф). В переменной res вычисляем наибольшее число ребер, которое может содержаться во всех компонентах, порожденных вершинами, подключенными к наружной сети. Присоединяем проводами множество из LeftVertex вершин к наибольшей компоненте связности: между LeftVertex вершинами можно провести LeftVertex * (LeftVertex – 1) / 2 ребер, между LeftVertex вершинами множества оставшихся ребер и MaxConnComp вершинами из наибольшей компоненты связности можно провести MaxConnComp * LeftVertex ребер. Остается из общего числа ребер res вычесть количество уже имеющихся Edges, чтобы найти максимальное число проводов, которое можно добавить.

Пример

Рассмотрим граф, приведенный во втором примере.

Красным обозначены вершины, подключенные к наружной сети. Зеленым пунктиром показаны провода, которые можно добавить в электрическую схему.

Реализация алгоритма

Электрическую сеть представляем в виде неориентированного графа и храним в виде матрицы смежности в массиве m. Массив used используется при поиске в глубину для отмечания уже пройденных вершин. Список вершин, подсоединенных к основной электросети, храним в массиве gridConnections.

int m[51][51], used[51];

vector<int> gridConnections;

Поиск в глубину используется для выделения компонент связности графа. В глобальной переменной Vertex подсчитываем количество вершин, входящих в текущую компоненту связности.

void dfs(int v)

{

int i;

used[v] = 1; Vertex++;

for(i = 0; i < n; i++)

if (m[v][i] && !used[i]) dfs(i);

}

Функция maxNewWires возвращает максимальное количество проводов, которое можно добавить в электрическую схему.

int maxNewWires(void)

{

int i, res = 0, LeftVertex = n, MaxConnComp = 0;

memset(used,0,sizeof(used));

Поскольку по условию задачи в каждую компоненту связности может входить максимум один внешний узел электросети, запускаем поиск в глубину из каждого такого узла.

for(i = 0; i < gridConnections.size(); i++)

{

Vertex = 0;

dfs(gridConnections[i]);

В компоненту связности, содержащую вершину gridConnections[i], входит Vertex вершин. Через Vertex вершин можно провести Vertex * (Vertex – 1) / 2 проводов. MaxConnComp содержит количество вершин в наибольшей компоненте связности.

res += Vertex * (Vertex - 1) / 2;

LeftVertex -= Vertex;

MaxConnComp = max(MaxConnComp,Vertex);

}

Осталось LeftVertex вершин, которые даже косвенно не связаны с внешними узлами электросети. Соединяем проводами все возможные пары этих (LeftVertex * (LeftVertex – 1) / 2 новых проводов), а также присоединяем каждую из них ко всем вершинам из наибольшей компоненты связности (MaxConnComp * LeftVertex новых проводов).

res += LeftVertex * (LeftVertex - 1) / 2 + MaxConnComp * LeftVertex;

return res - Edges;

}

Основная часть программы. Читаем входные данные. Подсчитываем количество ребер в графе Edges.

while(scanf("%d",&n) == 1)

{

for(Edges = i = 0; i < n; i++)

for(j = 0; j < n; j++)

{

scanf("%1d",&m[i][j]);

if (m[i][j]) Edges++;

}

scanf("%d",&num); gridConnections.clear();

for(i = 0; i < num; i++)

scanf("%d",&val), gridConnections.push_back(val);

Поскольку граф неориентированный, то каждое ребро будет посчитано дважды.

Edges /= 2;

Вычисляем и выводим ответ.

res = maxNewWires();

printf("%d\n",res);

}