Untitled
unknown
plain_text
a year ago
2.9 kB
2
Indexable
Never
package day12_1406; import java.io.FileInputStream; import java.io.FileNotFoundException; import java.util.Scanner; public class well_project { static int n; static int value; static int[][] map; static int[] parent, key; static boolean[] visit; private static int minKey(){ int min = Integer.MAX_VALUE; int min_idx = -1; for(int i = 0; i < n; i++){ if(!visit[i] && min > key[i]){ min = key[i]; min_idx = i; } } return min_idx; } private static void prim(){ key[0] = 0; for(long i = 0; i < n; i++){ int node = minKey(); visit[node] = true; for(int j = 0; j < n; j++){ if(!visit[j] && map[node][j] != 0 && map[node][j] < key[j]){ key[j] = map[node][j]; } } } } static boolean isValidEdge(int u, int v, boolean[] inMST) { if (u == v) return false; if (inMST[u] == false && inMST[v] == false) return false; else if (inMST[u] == true && inMST[v] == true) return false; return true; } private static void primv2(){ boolean []inMST = new boolean[n]; inMST[0] = true; int edge_count = 0, mincost = 0; while (edge_count < n - 1) { // Find minimum weight valid edge. int min = Integer.MAX_VALUE, a = -1, b = -1; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (map[i][j] < min) { if (isValidEdge(i, j, inMST)) { min = map[i][j]; a = i; b = j; } } } } if (a != -1 && b != -1) { edge_count++; mincost = mincost + min; inMST[b] = inMST[a] = true; } } value = mincost; } public static void main(String[] args) { // TODO Auto-generated method stub try { System.setIn(new FileInputStream("D:\\Trainee\\SRV_training\\src\\day12_1406\\WellProject.txt")); } catch (FileNotFoundException e) { // TODO Auto-generated catch block e.printStackTrace(); } Scanner sc = new Scanner(System.in); int testcase = sc.nextInt(); for(int tc = 1; tc <= testcase; tc++){ n = sc.nextInt(); map = new int[n][n]; parent = new int[n]; key = new int[n]; visit = new boolean[n]; for(int i = 0; i < n; i++){ key[i] = Integer.MAX_VALUE; } for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ map[i][j] = sc.nextInt(); } } value = 0; primv2(); // for(int i = 0; i < n; i++){ // value += key[i]; // } System.out.println("Case #" + tc); System.out.println(value); } } }