Untitled

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

}