Матч 410, Добавить провода (AddElectricalWires)

Дивизион 2, Уровень 2; Дивизион 1, Уровень 1

У Вас дома имеется электрическая цепь, представленная в виде графа. Ребрами графа являются провода, а вершинами – точки их соединения. Любая пара вершин соединена не более чем одним проводом, никакая вершина не соединена сама с собой. Каждая вершина является либо розеткой, либо точкой подключения к наружной сети электропитания.

Массив wires описывает множество имеющихся проводов. Массив gridConnections описывает множество вершин, подключенных к наружной сети.

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

Класс: AddElectricalWires

Метод: int maxNewWires(vector<string> wires,

vector<int> gridConnections)

Ограничения: wires и gridConnections содержат от 1 до 50 элементов, wires[i][j] содержит ‘0’ или ‘1’, wires[i][i] = ‘0’, wires[i][j] = wires[j][i], все элементы gridConnections разные, никакая пара вершин из gridConnections не связана проводами (даже не напрямую).

Вход. Массив wires описывает множество имеющихся проводов. Массив gridConnections описывает множество вершин, подключенных к наружной сети.

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

Пример входа

wires	gridConnections
{"000","000","000"}	{0}
{"000","000","000"}	{0,1}
{"01000","10100","01010","00100","00000"}	{2,4}

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

3

1

3

РЕШЕНИЕ

поиск в глубину

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

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

ПРОГРАММА

#include <cstdio>

#include <vector>

#include <string>

#include <memory>

using namespace std;

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

void dfs(int v)

{

int i;

used[v] = 1; Vertex++;

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

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

}

class AddElectricalWires

{

public:

int maxNewWires(vector<string> wires, vector<int> gridConnections)

{

int i, j, res = 0, LeftVertex, Edges = 0, MaxConnComp = 0;

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

LeftVertex = n = wires.size();

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

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

if (m[i][j] = (wires[i][j] == '1')) Edges++;

Edges /= 2; // graph is NOT oriented, every edge is counted twice

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

{

Vertex = 0;

dfs(gridConnections[i]);

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

LeftVertex -= Vertex;

MaxConnComp = max(MaxConnComp,Vertex);

}

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

return res - Edges;

}

};