Yeraltı kabellər (Həll təhlili)

Məsələni həll etmək üçün minimal örtən ağacı tapmaq lazımdır. Bunun üçün Prim alqoritmini realizə edəcəyik.

Nümunə

Nümunədə verilmiş iki qrafı quraq.

Alqoritmin realizasiyası

Qlobal massivləri elan edək. Nöqtələrin koordinatlarını $x[i]$ və $y[i]$ massivlərində saxlayacağıq.

#define MAX 1001
#define INF 0x3F3F3F3F

int x[MAX], y[MAX];
int used[MAX], dist[MAX];

dist2 funksiyası $i$ və $j$ nöqtələri arasındakı məsafənin kvadratını hesablayır.

int dist2(int i, int j)
{
  return (x[j] - x[i])*(x[j] - x[i]) + (y[j] - y[i])*(y[j] - y[i]);
}

Prim funksiyası Prim alqoritmini realizə edir və minimal örtən ağacın çəkisini qaytarır.

double Prim(void)
{

Massivləri ilkinləşdiririk.

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

Minimal örtən ağacın qurulmasına $0$ nömrəli təpədən başlayırıq. dist[0] = 0 və used[0] = 1 təyin edirik. $res$ dəyişənində minimal örtənin çəkisinin cəmi toplanır.

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

n - 1 iterasiya icra edirik. Hər iterasiyada örtənə bir təpə əlavə edirik (beləliklə, ümumilikdə n - 1 təpə əlavə etmək lazımdır).

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

Cari təpəni $cur$ kimi işarə edirik. (cur, j) tilləri üzrə keçid edərək dist[j] qiymətlərini yeniləyirik. Nəticədə dist[j] $j$ təpəsindən artıq qurulmuş minimal örtən ağacın hissəsinə qədər olan cari ən qısa məsafəni saxlayır.

    for (j = 0; j < n; j++)
      if (!used[j] && (dist2(cur, j) < dist[j]))
        dist[j] = dist2(cur, j);

Örtənə əlavə ediləcək ən kiçik uzunluqlu tili axtarırıq. Bunun üçün hələ örtənə daxil olmayan (used[j] = 0) təpələr arasında dist[j]-in minimal qiymətini tapırıq. Minimal dist[j] qiymətinə malik təpənin nömrəsini $cur$ dəyişənində saxlayırıq — o, cari təpə olur.

    int min = INF;
    for (j = 0; j < n; j++)
      if (!used[j] && (dist[j] < min))
      {
        min = dist[j];
        cur = j;
      }

$cur$ təpəsi örtənə daxil edilir, uzunluğu sqrt(dist[cur]) olan til isə minimal örtən ağaca əlavə edilir.

    used[cur] = 1;
    res += sqrt(dist[cur]);
  }
  return res;
}

Proqramın əsas hissəsi. Testləri ardıcıl olaraq emal edirik.

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

Nöqtələrin koordinatlarını oxuyuruq.

  for (i = 0; i < n; i++)
    scanf("%d %d", &x[i], &y[i]);

Minimal örtən ağacın çəkisini hesablayıb çıxarırıq.

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

Alqoritmin realizasiyası – min_e / end_e

Qlobal massivləri elan edək. Nöqtələrin koordinatlarını $x[i]$ və $y[i]$ massivlərində saxlayacağıq.

#define MAX 1010
int x[MAX], y[MAX];
int used[MAX], min_e[MAX], end_e[MAX];

dist2 funksiyası $i$ və $j$ nöqtələri arasındakı məsafənin kvadratını hesablayır.

int dist2(int i, int j)
{
  return (x[j] - x[i])*(x[j] - x[i]) + (y[j] - y[i])*(y[j] - y[i]);
}

Proqramın əsas hissəsi. Testləri ardıcıl olaraq emal edirik.

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

Nöqtələrin koordinatlarını oxuyuruq.

  for (i = 0; i < n; i++)
    scanf("%d %d", &x[i], &y[i]);

Massivləri ilkinləşdiririk.

  memset(min_e, 0x3F, sizeof(min_e));
  memset(end_e, -1, sizeof(end_e));
  memset(used, 0, sizeof(used));

Minimal örtən ağacın çəkisi $dist$ dəyişənində toplanacaq.

  dist = min_e[1] = 0;
  for (i = 0; i < n; i++)
  {

Hələ minimal örtənə daxil edilməyən (used[v] = 0) təpələr arasında $min\_e[v]$-in minimal qiymətinə malik $v$ təpəsini axtarırıq.

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

$v$ təpəsini örtənə daxil edirik və (v, end\_e[v]) tilini ona əlavə edirik.

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

$v$ təpəsindən çıxan (v, to) tilləri üçün etiketləri yeniləyirik. Keçidi yalnız hələ minimal örtən ağaca daxil edilməyən (used[to] = 0) $to$ təpələri üzrə həyata keçiririk.

    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;
      }
    }
  }

Minimal örtən ağacın çəkisini çıxarırıq.

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