USACO DEC07 Problem 'roads' Analysis

by Richard Peng

We note that since all edges have non-negative weights, there will not be a cycle in the final version of the graph. Thus, this problem is equivalent to finding the minimum spanning tree in a graph where the edge weights are the Euclidean distances (with the exception of a few whose distances are set to zero).

Several minimum spanning tree algorithms can be use here. Since we're finding the MST of a dense graph, the best option is probably the O(n^2) version of the Prim algorithm:

• Start with the tree being a single vertex
• Keep a list of distances of every other vertex to the tree
• At each iteration
  • Add the closest vertex to the tree
  • Update the distances accordingly.

This runs in O(n^2) time, which suffices for this problem.

By the way: This problem can actually be done in O(nlogn+m) time. The idea is basically the edges that could potentially be in the minimum spanning tree must belong to what's known as the Delaunay triangulation, which has O(n) edges. We can find the Delaunary triangulation in O(nlogn) time and apply a fast version of Kruskal's algorithm for sparse graphs to get the desired runtime.

Below is Chinese sophomore ShiMen Xu's compact solution (which might or might not match the description above):

#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;

ifstream fin ("roads.in");

struct Tpoint {
    long long x, y;
};
Tpoint	p[1010];
double	dis[1010];
int	N, M;

int	us  [1010];
double	ans;

void	init ();
int	findRoot (int i);
void	work ();

int 
main () {
    FILE   *f = fopen ("roads.out", "w");
    init ();
    work ();
    fprintf (f, "%0.2lf\n", ans);
    return 0;
}

int 
findRoot (int i) {
    if (us[i] == i)
	return i;
    return us[i] = findRoot (us[i]);
}

void 
init () {
    fin >> N >> M;
    for (int i = 1; i <= N; i++)
	fin >> p[i].x >> p[i].y;

    for (int i = 0; i <= N; i++)
	us[i] = i;

    for (int i = 0; i < M; i++) {
	int	a  , b, a1, b1;
	fin >> a >> b;
	if ((a1 = findRoot (a)) != (b1 = findRoot (b)))
	    us[a1] = b1;
    }
}

void 
work () {
    int	    root, cnt[1010], id;

    root = findRoot (1);
    memset (cnt, 0, sizeof (cnt));
    for (int i = 0; i <= N; i++)
	dis[i] = 10000000.0 * 1000000.0;
    for (id = 1;; id++) {
	for (int i = 1; i <= N; i++)
	    if (cnt[i] == 0)
		if (root == findRoot (i))
		    cnt[i] = id;
	double	mindis = dis[0];
	int	minj = 0;

	for (int i = 1; i <= N; i++)
	    if (cnt[i] == id)
		for (int j = 2; j <= N; j++)
		    if (cnt[j] == 0) {
			double	d1 = sqrt ((p[j].x - p[i].x) * (p[j].x - p[i].x) +
                                              (p[j].y - p[i].y) * (p[j].y - p[i].y));
			dis[j] <? = d1;
			if (dis[j] < mindis) {
			    mindis = dis[j];
			    minj = j;
			}
		    }
	if (minj == 0)
	    break;
	int	j1 = findRoot (minj);
	ans += mindis;
	us[j1] = root;
    }
}