1258 - グラフな問題
2011/09/23
java
pku
poj
prim
1258 -- Agri-Net
Javaです。グラフな問題にチャレンジということで。
解き方は、
プログラミングコンテストチャレンジブック 秋葉 拓哉 岩田 陽一 北川 宜稔 
p.100を参考にしています。
僕自身プリム法よくわかってないです。たくさんとけばなんとなくわかってくるかなと....
プリム法 - Wikipedia
package p1258;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while (scanner.hasNext()) {// これいれないとだめ
int n = scanner.nextInt();
int V = n;
int[][] cost = new int[V][V];
int[] d = new int[V];
boolean[] used = new boolean[V];
int[] mincost = new int[V];
{
for (int i = 0; i < V; i++) {
used[i] = false;
d[i] = 0;
mincost[i] = 0;
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cost[i][j] = scanner.nextInt();
}
}
mincost[0] = 0;
int res = 0;
while (true) {
int v = -1;
for (int u = 0; u < V; u++) {
if (!used[u] && (v == -1 || mincost[u] < mincost[v]))
v = u;
}
if (v == -1)
break;
used[v] = true;
res += mincost[v];
for (int u = 0; u < V; u++) {
if (mincost[u] == 0) {
mincost[u] = cost[v][u];
continue;
}
mincost[u] = Math.min(mincost[u], cost[v][u]);
}
}
int a = d[0];
for (int i = 1; i < d.length; i++) {
a = Math.min(a, d[i]);
}
System.out.println(res);
}
}
}
: