Cavi sotterranei#1387

Cavi sotterranei (Editoriale)

Per risolvere il problema è necessario trovare l'albero ricoprente minimo. A tal fine implementiamo l'algoritmo di Prim.

Esempio

Costruiamo i due grafi riportati nell'esempio.

Implementazione dell'algoritmo

Dichiariamo gli array globali. Le coordinate dei punti verranno memorizzate negli array $x [i]$ e $y [i]$ .

#define MAX 1001
#define INF 0x3F3F3F3F

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

La funzione dist2 calcola il quadrato della distanza tra i punti $i$ e $j$ .

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

La funzione Prim implementa l'algoritmo di Prim e restituisce il peso dell'albero ricoprente minimo.

double Prim(void)
{

Inizializziamo gli array.

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

Iniziamo la costruzione dell'albero ricoprente minimo a partire dal vertice $0$ . Impostiamo $d i s t [0] = 0$ dist[0] = 0 e $u se d [0] = 1$ used[0] = 1. Nella variabile $r es$ si accumula il valore del peso dell'albero ricoprente minimo.

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

Eseguiamo $n - 1$ n - 1 iterazioni. Ad ogni iterazione aggiungiamo un vertice all'albero ricoprente (in totale è quindi necessario aggiungere $n - 1$ n - 1 vertici).

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

Il vertice corrente viene indicato come $c u r$ . Scorriamo gli archi $(c u r, j)$ (cur, j) e aggiorniamo i valori di $d i s t [j]$ dist[j]. Di conseguenza, $d i s t [j]$ dist[j] memorizza la distanza minima corrente dal vertice $j$ alla parte già costruita dell'albero ricoprente minimo.

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

Cerchiamo l'arco di lunghezza minima che verrà aggiunto all'albero ricoprente. Per farlo, troviamo il valore minimo di $d i s t [j]$ dist[j] tra i vertici $j$ che non appartengono ancora all'albero ricoprente ( $u se d [j] = 0$ used[j] = 0). Il numero del vertice con il valore minimo di $d i s t [j]$ dist[j] viene salvato nella variabile $c u r$ — esso diventa il vertice corrente.

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

C++

Il vertice $c u r$ viene incluso nell'albero ricoprente, e l'arco di lunghezza $s q r t (d i s t [c u r])$ sqrt(dist[cur]) viene aggiunto all'albero ricoprente minimo.

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

Parte principale del programma. Elaboriamo i test in sequenza.

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

Leggiamo le coordinate dei punti.

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

Calcoliamo e stampiamo il peso dell'albero ricoprente minimo.

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

Implementazione dell'algoritmo – min_e / end_e

Dichiariamo gli array globali. Le coordinate dei punti verranno memorizzate negli array $x [i]$ e $y [i]$ .

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

La funzione dist2 calcola il quadrato della distanza tra i punti $i$ e $j$ .

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

Parte principale del programma. Elaboriamo i test in sequenza.

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

Leggiamo le coordinate dei punti.

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

Inizializziamo gli array.

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

Il peso dell'albero ricoprente minimo verrà accumulato nella variabile $d i s t$ .

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

Cerchiamo il vertice $v$ con il valore minimo di $min_e [v]$ tra i vertici non ancora inclusi nell'albero ricoprente minimo ( $u se d [v] = 0$ used[v] = 0).

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

Includiamo il vertice $v$ nell'albero ricoprente e aggiungiamo ad esso l'arco $(v, e n d_e [v])$ (v, end\_e[v]).

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

Aggiorniamo le etichette per gli archi $(v, t o)$ (v, to), uscenti dal vertice $v$ . Il ciclo viene eseguito solo sui vertici $t o$ che non sono ancora stati inclusi nell'albero ricoprente minimo $(u se d [t o] = 0)$ (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;
      }
    }
  }

C++

Stampiamo il peso dell'albero ricoprente minimo.

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