Underground Cables#1387

Underground Cables (Editorial)

To solve the problem, it is necessary to find a minimum spanning tree. For this purpose, we implement Prim's algorithm.

Example

Let us construct the two graphs given in the example.

Algorithm implementation

Declare global arrays. The coordinates of the points will be stored in the arrays $x [i]$ and $y [i]$ .

#define MAX 1001
#define INF 0x3F3F3F3F

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

The function dist2 computes the squared distance between points $i$ and $j$ .

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

The Prim function implements Prim’s algorithm and returns the weight of the minimum spanning tree.

double Prim(void)
{

Initialize the arrays.

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

We start constructing the minimum spanning tree from vertex $0$ . Set $d i s t [0] = 0$ dist[0] = 0 and $u se d [0] = 1$ used[0] = 1. The variable $r es$ accumulates the total weight of the minimum spanning tree.

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

We perform $n - 1$ n - 1 iterations. At each iteration, we add one vertex to the spanning tree (thus, a total of $n - 1$ n - 1 vertices must be added).

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

The current vertex is denoted as $c u r$ . We iterate over the edges $(c u r, j)$ (cur, j) and update the values of $d i s t [j]$ dist[j]. As a result, $d i s t [j]$ dist[j] stores the current shortest distance from vertex $j$ to the already constructed part of the minimum spanning tree.

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

We search for the edge of minimum length to be added to the spanning tree. To do this, we find the minimum value of $d i s t [j]$ dist[j] among the vertices $j$ that do not yet belong to the tree ( $u se d [j] = 0$ used[j] = 0). The index of the vertex with the minimum $d i s t [j]$ dist[j] value is stored in the variable $c u r$ , which becomes the current vertex.

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

C++

The vertex $c u r$ is then included in the spanning tree, and the edge of length $s q r t (d i s t [c u r])$ sqrt(dist[cur]) is added to the minimum spanning tree.

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

The main part of the program. Process the test cases sequentially.

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

Read the coordinates of the points.

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

Compute and print the weight of the minimum spanning tree.

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

Algorithm implementation – min_e / end_e

Declare global arrays. The coordinates of the points will be stored in the arrays $x [i]$ and $y [i]$ .

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

The function dist2 computes the squared distance between points $i$ and $j$ .

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

The main part of the program. Process the test cases sequentially.

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

Read the coordinates of the points.

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

Initialize the arrays.

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

The weight of the minimum spanning tree will be accumulated in the variable $d i s t$ .

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

We find the vertex $v$ with the minimum value $min_e [v]$ among the vertices that have not yet been included in the minimum spanning tree ( $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;

Include the vertex $v$ in the spanning tree and add the edge $(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]));

Update the labels for the edges $(v, t o)$ (v, to) outgoing from vertex $v$ . The iteration is performed only over the vertices $t o$ that have not yet been included in the minimum spanning tree $(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++

Print the weight of the minimum spanning tree.

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