1387. Подземные кабеля

 

Город планирует избавиться от неприглядных электрических столбов, проложив кабели под землёй. Имеется список точек, которые необходимо соединить, однако существуют определённые ограничения. Оборудование для прокладки туннелей может перемещаться только по прямым линиям между заданными точками. В любой точке, кроме указанных, может проходить не более одного подземного кабеля, поэтому никакие два кабеля не должны пересекаться.

Дан набор точек. Определите минимальную суммарную длину кабеля, необходимую для того, чтобы каждая пара точек была соединена либо напрямую, либо через другие точки.

 

Вход. Содержит несколько тестов. Каждый тест начинается с целого числа n (2 ≤ n ≤ 1000) – количества точек в городе. В каждой из следующих n строк заданы два целых числа x и y (-1000 ≤ x, y ≤ 1000) – координаты точки (x, y). Все точки в пределах одного теста различны. Последняя строка содержит 0 и не обрабатывается.

 

Выход. Для каждого теста выведите одно вещественное число — минимальную длину кабеля, необходимую для соединения всех городских точек, с точностью до двух десятичных знаков.

 

Пример входа

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

4

0 0

0 10

10 0

10 10

2

0 0

10 10

0

30.00

14.14

 

 

РЕШЕНИЕ

графы – алгоритм Прима

 

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

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

 

Пример

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

 

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

Объявим глобальные массивы. Координаты точек будем хранить в массивах x[i] и y[i].

 

#define MAX 1001

#define INF 0x3F3F3F3F

 

int x[MAX], y[MAX];

int used[MAX], dist[MAX];

 

Функция dist2 вычисляет квадрат расстояния между точками i и j.

 

int dist2(int i, int j)

{

  return (x[j] - x[i])*(x[j] - x[i]) + (y[j] - y[i])*(y[j] - y[i]);

}

 

Функция Prim реализует алгоритм Прима и возвращает вес минимального остовного дерева.

 

double Prim(void)

{

 

Инициализируем массивы.

 

  memset(dist, 0x3F, sizeof(dist));

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

 

Начинаем построение минимального остовного дерева с вершины 0. Устанавливаем dist[0] = 0 и used[0] = 1. В переменной res накапливается значение веса минимального остова.

 

  double res = 0;

  int i, j, cur = 0;

  dist[cur] = 0;

  used[cur] = 1;

 

Выполняем n – 1 итераций. На каждой итерации добавляем в остов одну вершину (таким образом, всего необходимо добавить n – 1 вершин).

 

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

  {

 

Текущая вершина обозначается как cur. Перебираем ребра (cur, j) и обновляем значения dist[j]. В результате dist[j] хранит текущее кратчайшее расстояние от вершины j до уже построенной части минимального остовного дерева.

 

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

      if (!used[j] && (dist2(cur, j) < dist[j]))

        dist[j] = dist2(cur, j);

 

Ищем ребро наименьшей длины, которое будет добавлено в остов. Для этого находим минимальное значение dist[j] среди вершин j, ещё не принадлежащих остову (used[j] = 0). Номер вершины с минимальным значением dist[j] сохраняем в переменной cur – она становится текущей вершиной.

 

    int min = INF;

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

      if (!used[j] && (dist[j] < min))

      {

        min = dist[j];

        cur = j;

      }

 

Вершина cur включается в остов, а ребро длины sqrt(dist[cur]) добавляется к минимальному остовному дереву.

 

    used[cur] = 1;

    res += sqrt(dist[cur]);

  }

  return res;

}

 

Основная часть программы. Последовательно обрабатываем тесты.

 

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

{

 

Читаем координаты точек.

 

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

    scanf("%d %d", &x[i], &y[i]);

 

Вычисляем и выводим вес минимального остовного дерева.

 

  res = Prim();

  printf("%.2lf\n", res);

}

 

Реализация алгоритма – min_e / end_e

Объявим глобальные массивы. Координаты точек будем хранить в массивах x[i] и y[i].

 

#define MAX 1010

int x[MAX], y[MAX];

int used[MAX], min_e[MAX], end_e[MAX];

 

Функция dist2 вычисляет квадрат расстояния между точками i и j.

 

int dist2(int i, int j)

{

  return (x[j] - x[i])*(x[j] - x[i]) + (y[j] - y[i])*(y[j] - y[i]);

}

 

Основная часть программы. Последовательно обрабатываем тесты.

 

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

{

 

Читаем координаты точек.

 

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

    scanf("%d %d", &x[i], &y[i]);

 

Инициализируем массивы.

 

  memset(min_e, 0x3F, sizeof(min_e));

  memset(end_e, -1, sizeof(end_e));

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

 

Вес минимального остовного дерева будет накапливаться в переменной dist.

 

  dist = min_e[1] = 0;

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

  {

 

Ищем вершину v с минимальным значением min_e[v] среди вершин, ещё не включённых в минимальный остов (used[v] = 0).

 

    v = -1;

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

      if (!used[j] && (v == -1 || min_e[j] < min_e[v])) v = j;

 

Включаем вершину v в остов и добавляем в него ребро (v, end_e[v]).

 

    used[v] = 1;

    if (end_e[v] != -1) dist += sqrt((double)dist2(v, end_e[v]));

 

Обновляем метки для рёбер (v, to), исходящих из вершины v. Перебор выполняем только по вершинам to, которые ещё не включены в минимальное остовное дерево (used[to] = 0).

 

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

    {

      int dV_TO = dist2(v, to);

      if (!used[to] && (dV_TO < min_e[to]))

      {

        min_e[to] = dV_TO;

        end_e[to] = v;

      }

    }

  }

 

Выводим вес минимального остовного дерева.

 

  printf("%.2lf\n", dist);

}