1107. ACM соревнование и нарушение связи

Для подготовки к “Первому национальному школьному ACM соревнованию”(в 20??) мэр города решил обеспечить все школы надежным источником энергии. (Мэр очень боится нарушения связи). Для этого электростанция “Будущее” и одна из школ (не имеет значение какая) должны быть соединены; а также некоторые другие школы также должны быть присоединены к сети.

Школа имеет достаточно электроэнергии, если либо она присоединена напрямую к электростанции “Будущее”, либо к другой школе, имеющую достаточно электроэнергии. Вам известна стоимость соединения некоторых школ друг с другом. Мэр желает найти два самых дешевых плана соединения школ. Стоимость плана равна сумме стоимостей всех входящих в него соединений между школами. Помогите мэру найти эти два самых дешевых плана.

Вход. Первая строка содержит два числа, разделенных одним пробелом: N (3 ≤ N ≤ 100) – количество школ в городе и M – количество имеющихся связей между ними. Каждая из следующих M строк содержит три числа A_i, B_i, C_i , где C_i -- стоимость связи (1 ≤ C_i ≤ 300) между школами A_i и B_i. Школы пронумерованы целыми числами от 1 до N.

Выход. В одной строке вывести два числа, разделенные одним пробелом: стоимости двух самых дешевых планов соединений. Пусть S1 – самый дешевый план, а S2 второй по дешевизне план. Тогда S1 = S2 только если это два самых дешевых плана, иначе S1 ≤ S2. Считайте, что всегда можно найти S1 и S2.

Пример входа	Пример выхода
5 8 1 3 75 3 4 51 2 4 19 3 2 95 2 5 42 5 4 31 1 2 9 3 5 66	110 121

РЕШЕНИЕ

графы – первый и второй минимальный остов

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

Самый дешевый план – это минимальное остовное дерево. Чтобы построить второе минимальное остовное дерево, необходимо:

1. Найти первый минимальный остов и запомнить ребра, в него входящие.

2. Перебираем ребра первого минимального остова: исключаем ребро из исходного графа, вычисляем его минимальный остов. При этом полученный остов должен оставаться связным (если число вершин в графе n, то количество ребер в остове должно равняться n – 1). Находим минимум среди всех таких полученных остовов – это и есть величина второго минимального остовного дерева.

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

Объявим рабочие константы и структуры. Ребра графа храним в массиве е. Массив MSTEdges хранит номера ребер, из которых состоит первый MST.

#define MAXV 110

#define INF 2000000000

struct Edge

{

int u, v, dist;

Edge(int u = 0, int v = 0, int dist = 0) : u(u), v(v), dist(dist) {}

};

vector<Edge> e;

vector<int> MSTEdges;

int mas[MAXV], size[MAXV];

Читаем входные данные.

scanf("%d %d",&n,&m);

for(i = 1; i <= n; i++) mas[i] = i, size[i] = 1;

Читаем ребра графа.

e.clear(); MSTEdges.clear();

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

{

scanf("%d %d %d",&temp.u,&temp.v,&temp.dist);

e.push_back(temp);

}

Сортируем ребра графа по возрастанию длины.

sort(e.begin(),e.end(),lt);

Находим величину первого минимального остова MST1.

MST1 = 0;

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

if (Union(e[i].u,e[i].v))

{

MST1 += e[i].dist;

MSTEdges.push_back(i);

}

Находим величину второго минимального остова MST2.

MST2 = INF;

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

{

len = 0;

cnt = 1;

Инициализируем систему непересекающихся множеств.

for(j = 1; j <= n; j++) mas[j] = j, size[j] = 1;

Перебираем ребра исходного графа. Ищем величину минимального остова len, в котором исключено ребро номер MSTEdges[i]. Находим минимум среди всех таких минимальных остовов – это и есть второй по величине MST.

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

{

if (j == MSTEdges[i]) continue;

if (Union(e[j].u,e[j].v))

{

len += e[j].dist;

cnt++;

}

}

Полученный остов должен соединять n вершин (например если MSTEdges[i] является мостом в графе, то полученная конструкция не будет соединять все n вершин и не будет остовом). Ищем минимум MST2 среди всех полученных остовов.

if ((cnt == n) && (len < MST2))

MST2 = len;

}

Выводим ответ.

printf("%d %d\n",MST1,MST2);