Підземні кабелі#1387

Підземні кабелі (Розбір)

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

Приклад

Побудуємо два графи, наведені у прикладі.

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

Оголосимо глобальні масиви. Координати точок будемо зберігати у масивах $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$ . Встановлюємо $d i s t [0] = 0$ dist[0] = 0 та $u se d [0] = 1$ used[0] = 1. У змінній $r es$ накопичується значення ваги мінімального остова.

  double res = 0;
  int i, j, cur = 0;
  dist[cur] = 0;
  used[cur] = 1;

Виконуємо $n - 1$ n - 1 ітерацій. На кожній ітерації додаємо до остова одну вершину (таким чином, загалом необхідно додати $n - 1$ n - 1 вершин).

  for (i = 1; i 

Поточна вершина позначається як $cur$. Перебираємо ребра $(cur, j)$ та оновлюємо значення $dist[j]$. У результаті $dist[j]$ зберігає поточну найкоротшу відстань від вершини $j$ до вже побудованої частини мінімального остовного дерева.

\begin{lstlisting}[language=C++]
    for (j = 0; j 

Шукаємо ребро найменшої довжини, яке буде додано до остова. Для цього знаходимо мінімальне значення $dist[j]$ серед вершин $j$, які ще не належать остову ($used[j] = 0$). Номер вершини з мінімальним значенням $dist[j]$ зберігаємо у змінній $cur$ --- вона стає поточною вершиною.

\begin{lstlisting}[language=C++]
    int min = INF;
    for (j = 0; j 

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

\begin{lstlisting}[language=C++]
    used[cur] = 1;
    res += sqrt(dist[cur]);
  }
  return res;
}

C++

Основна частина програми. Послідовно обробляємо тести.

while (scanf("%d", 

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

\begin{lstlisting}[language=C++]
  for (i = 0; i 

Обчислюємо та виводимо вагу мінімального остовного дерева.

\begin{lstlisting}[language=C++]
  res = Prim();
  printf("%.2lf\n", res);
}

C++

Реалізація алгоритму – 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", 

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

\begin{lstlisting}[language=C++]
  for (i = 0; i 

Ініціалізуємо масиви.

\begin{lstlisting}[language=C++]
  memset(min_e, 0x3F, sizeof(min_e));
  memset(end_e, -1, sizeof(end_e));
  memset(used, 0, sizeof(used));

C++

Вага мінімального остовного дерева буде накопичуватися у змінній $d i s t$ .

  dist = min_e[1] = 0;
  for (i = 0; i 

Шукаємо вершину $v$ з мінімальним значенням $min\_e[v]$ серед вершин, які ще не включені до мінімального остова ($used[v] = 0$).

\begin{lstlisting}[language=C++]
    v = -1;
    for (j = 0; j 

Включаємо вершину $v$ до остова та додаємо до нього ребро $(v, end\_e[v])$.

\begin{lstlisting}[language=C++]
    used[v] = 1;
    if (end_e[v] != -1) dist += sqrt((double)dist2(v, end_e[v]));

C++

Оновлюємо мітки для ребер $(v, t o)$ (v, to), що виходять з вершини $v$ . Перебір виконуємо тільки по вершинах $t o$ , які ще не включені до мінімального остовного дерева $(u se d [t o] = 0)$ (used[to] = 0).

    for (to = 0; to 
    {
      int dV_TO = dist2(v, to);
      if (!used[to] 
      {
        min_e[to] = dV_TO;
        end_e[to] = v;
      }
    }
  }

C++

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

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