# Agri-Net (POJ 1258)

The optimal fiber connection is in fact a minimum spanning tree of the origin networks. We use Prim algorithm to get minimum spanning tree.

import java.io.*;
import java.util.*;

class Edge implements Comparable<Edge> {
int u;
int v;
int d;

public Edge(int u, int v, int d) {
this.u = u;
this.v = v;
this.d = d;
}

public int compareTo(Edge b) {
return this.d - b.d;
}
}

public class AgriNet {
private static int prim(int[][] costs) {
int N = costs.length;

int sum = 0;
boolean[] used = new boolean[N];
used[0] = true;

PriorityQueue<Edge> que = new PriorityQueue<Edge>(N);
for (int i = 1; i < N; i++) que.offer(new Edge(0, i, costs[0][i]));

while (!que.isEmpty()) {
Edge e = que.poll();

if (used[e.v]) continue;

sum += e.d;
used[e.v] = true;

for (int i = 0; i < N; i++) {
if (used[i]) continue;
que.offer(new Edge(e.v, i, costs[e.v][i]));
}
}

return sum;
}

public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNextInt()) {
int N = in.nextInt();
int[][] costs = new int[N][N];

for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
costs[i][j] = in.nextInt();
}
}

System.out.println(prim(costs));
}
}
}