Loading...

1258 - グラフな問題

1258 -- Agri-Net
Javaです。グラフな問題にチャレンジということで。
解き方は、
プログラミングコンテストチャレンジブック 秋葉 拓哉 岩田 陽一 北川 宜稔 4839931992
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); } } }
リアクション: 
prim 2636674745250027244

コメントを投稿

ホーム item

このブログを検索

Random Posts

Popular Posts

Labels

ADS