Untitled
plain_text
a month ago
5.5 kB
2
Indexable
Never
package tctt; import java.io.FileInputStream; import java.util.Scanner; public class Solution { static int[][] a; static int[] chuaxet; static boolean cycle; static int n, k; static int[] b; static int[] c; static int min, td1, td2; static int td; public static void main(String args[]) throws Exception{ System.setIn(new FileInputStream("src/tctt/input.txt")); Scanner sc = new Scanner(System.in); int T; int Answer; T=sc.nextInt(); for(int test_case = 1; test_case <= T; test_case++){ n = sc.nextInt(); b = new int[n]; a = new int[n][n]; for(int i = 0; i < n; i++){ int x = sc.nextInt(); b[i] = sc.nextInt(); int z = sc.nextInt(); for(int j = 0; j < z; j++){ int y = sc.nextInt(); a[x][y] = 1; } } /*for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ System.out.print(a[i][j] + " "); } System.out.println(); } */ chuaxet = new int[n]; for(int i = 0; i < n; i++){ chuaxet[i] = 0; } int kq = 0; for(int i = 0; i < n; i++){ td = -1; cycle = false; c = new int[n]; k = 0; for(int j = 0; j < n; j++){ chuaxet[j] = 0; } dfs(i,i); while(cycle){ int res = td; int temp = -1; int[] h = new int[k]; int l = 0; for(int u = 0; u < k; u++){ if(chuaxet[c[u]] == 1){ h[l] = c[u]; l++; } } for(int u = 0; u < l; u++){ if(h[u] == res){ temp = u; break; } } min = b[h[temp]] + b[h[l-1]]; int x1 = h[temp], x2 = h[l-1];; for(int u = temp; u < l - 1; u++){ if(min > b[h[u]] + b[h[u+1]]){ min = b[h[u]] + b[h[u+1]]; x1 = h[u]; x2 = h[u+1]; } } kq += min; a[x1][x2] = 0; a[x2][x1] = 0; td = -1; cycle = false; c = new int[n]; k = 0; for(int j = 0; j < n; j++){ chuaxet[j] = 0; } dfs(i,i); } } System.out.println("Case #" + test_case); System.out.println(kq); } } public static void dfs(int pre, int v){ c[k] = v; k++; chuaxet[v] = 1; for(int i = 0; i < n; i++){ if(a[v][i] != 0 && chuaxet[i] == 0){ dfs(v, i); }else if(chuaxet[i] == 1 && a[v][i] != 0 && pre!= i){ td = i; cycle = true; //return; } if(cycle){ return; } } chuaxet[v] = 2; } } package tctt; import java.io.FileInputStream; import java.util.Scanner; public class SolutionDj { static int[][] a; static int[] chuaxet; static boolean cycle; static int n, k, sum; static int[] b; static int[] c; static int[][] x; public static void main(String args[]) throws Exception{ System.setIn(new FileInputStream("src/tctt/input.txt")); Scanner sc = new Scanner(System.in); int T; int Answer; T=sc.nextInt(); for(int test_case = 1; test_case <= T; test_case++){ n = sc.nextInt(); b = new int[n]; a = new int[n][n]; for(int i = 0; i < n; i++){ int x = sc.nextInt(); b[i] = sc.nextInt(); int z = sc.nextInt(); for(int j = 0; j < z; j++){ int y = sc.nextInt(); a[x][y] = 1; } } /*for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ System.out.print(a[i][j] + " "); } System.out.println(); }*/ x = new int[n][n]; for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ if(a[i][j] == 1){ x[i][j] = b[i] + b[j]; } } } /* System.out.println(); for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ System.out.print(x[i][j] + " "); } System.out.println(); } */ sum = 0; for(int i = 0; i < n-1; i++){ for(int j = i+1; j < n; j++){ sum += x[i][j]; } } //System.out.println("sum " + sum); prim(); //System.out.println("Case #" + test_case); //System.out.println(kq); } } public static void prim(){ int parent[] = new int[n]; int key[] = new int[n]; boolean visit[] = new boolean[n]; for (int i = 0; i < n; i++) { key[i] = -1; visit[i] = false; parent[i] = -1; } key[0] = 0; for (int i = 0; i < n - 1; i++) { int max = -1, td = -1; for (int j = 0; j < n; j++){ if (visit[j] == false && key[j] > max) { max = key[j]; td = j; } } int u = td; visit[u] = true; for (int k = 0; k < n; k++){ if (visit[k] == false){ if(x[u][k] > key[k]){ parent[k] = u; key[k] = x[u][k]; } } } } int tong = 0; for(int i = 1; i < n; i++){ // System.out.println(parent[i] + " - " + i + " " + key[i]); tong += key[i]; } System.out.println(sum-tong); } }