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