You are given an electrical circuit for a home, with a number
of nodes possibly connected by wires. Any pair of nodes may be connected by at
most one wire, and a node can't be connected to itself. Each node on the
circuit is either an electrical outlet for the house or a connection to the
main electrical grid.
You'd like to make the circuit safer and more redundant by
adding as many extra wires to it as possible. The one complication is that no
two main grid connections are currently wired together (directly or
indirectly), and you must preserve this, or else disaster will result.
Determine the maximum number of new wires you can add to the circuit.
Input. Consists of
multiple test cases. The first line of each test case contains the number n (1 ≤ n ≤ 50) of nodes, numbered with integers from 0 to n – 1. Next n lines describes the wires that are already in place: the x-th character of the y-th line is '1' (one) if nodes x and y have a wire between them, '0' (zero) otherwise. Next line gives
the number of nodes, connected to the main electrical grid, followed by the
list of these nodes.
Output. For each test case print in a separate line the
maximum number of new wires you can add to the circuit.
3
000
000
000
2 0 1
5
01000
10100
01010
00100
00000
2 2 4
1
3
graphs – depth first search
Построим матрицу смежности графа
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, чтобы
найти максимальное число проводов, которое можно добавить.
Algorithm
realization
Электрическую сеть представляем в виде
неориентированного графа и храним в виде матрицы смежности в массиве 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);
}