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