Analysis: Watering the Fields by Fatih Gelgi

The problem description easily reveals the Minimum Spanning Tree solution. Fields are vertices and squared Euclidean distance is the weight of the edge of a field pair. We just need to disregard the edges that are less than C. Then running MST will solve the problem. If there is a field that cannot be reached (all distances to that field is less than C), the output will be -1.

Representing the graph with adjacency matrix requires O(N^2) memory. We can use it since N is small. Note that representing the graph with an adjacency list is not necessary; in fact it complicates the problem. The running time of Prim's MST algorithm on adjacency matrix is also O(N^2) which is sufficient for the problem. The sample code is as follows:

/* MST with adjacency matrix: O(n^2) */
#include <fstream>

#define MAX 2000

using namespace std;

int n,c,x[MAX],y[MAX],mat[MAX][MAX];

// MST with Prim
int mst()
{
	int from[MAX];
	bool mark[MAX];
	fill(from,from+n,-1);
	fill(mark,mark+n,false);

	int x=0,l=0;			// start from vertex 0
					// initial length of MST is 0
	for (int i=0; i<n-1; i++)
	{
		mark[x]=true;

		// expand the vertex and update edges in the queue
		for (int j=0; j<n; j++)
			if (!mark[j])
				if (mat[x][j])	// if there is (x,j) edge
					if (from[j]==-1 || mat[from[j]][j]>mat[x][j])
						from[j]=x;

		// choose the unused edge with minimum length in the queue
		x=-1;
		for (int j=0; j<n; j++)
			if (!mark[j] && from[j]!=-1)
				if (x==-1 || mat[from[x]][x]>mat[from[j]][j])
					x=j;

		// if graph is not connected
		if (x==-1) return -1;

		// update total cost of mst
		l+=mat[from[x]][x];
	}

	return l;
}

int main()
{
	ifstream fin("irrigation.in");
	int m;
	fin >> n >> c;
	for (int i=0; i<n; i++)
		fin >> x[i] >> y[i];
	fin.close();

	// construct the MST graph
	for (int i=0; i<n; i++)
		for (int j=0; j<n; j++)
		{
			mat[i][j]=(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);
			// remove the edge from graph if cost is less than c
			if (mat[i][j]<c) mat[i][j]=0;
		}

	ofstream fout("irrigation.out");
	fout << mst() << endl;	// write total length of MST
	fout.close();
}

Although it is not necessary, we can optimize the memory usage and reduce it to O(N). Since the graph is in 2D plane, it is a fully connected graph i.e. any vertex pair has an edge between them. Hence we don't need to keep the matrix. Here's a sample code:

/* MST with Prim: O(n^2) */
#include <fstream>
#include <algorithm>

#define MAX 2000

using namespace std;

int n,c,x[MAX],y[MAX],dist[MAX];

int main()
{
	ifstream fin("irrigation.in");
	fin >> n >> c;
	for (int i=0; i<n; i++) fin >> x[i] >> y[i];
	fin.close();

	int k=0,l=0;			// start from vertex 0
					// initial length of MST is 0
	fill(dist,dist+n,1000000000);

	for (int i=0; i<n-1; i++)
	{
		dist[k]=-1;		// mark used vertices

		// explore vertices and update edges in the queue
		for (int j=0; j<n; j++)
		{
			int d=(x[k]-x[j])*(x[k]-x[j])+(y[k]-y[j])*(y[k]-y[j]);
			// if (x,j) edge is long enough
			if (d>=c && d<dist[j]) dist[j]=d;
		}

		// choose the unused edge with minimum length in the queue
		k=-1;
		for (int j=0; j<n; j++)
			if (dist[j]!=-1 && dist[j]!=1000000000)
				if (k==-1 || dist[k]>dist[j]) k=j;

		if (k==-1) break;	// if graph is not connected
		l+=dist[k];		// update total cost of mst
	}
	if (k==-1) l=-1;

	ofstream fout("irrigation.out");
	fout << l << endl;
	fout.close();
}