Untitled
unknown
plain_text
2 years ago
2.5 kB
5
Indexable
package Tan_Cong_Thanh_Tri; import java.io.FileInputStream; import java.util.Scanner; public class thanhTri { static int n; static int [][] matrix; static int [] visit; static int [] arr; static int min; static int sum; static void reset() { for (int i = 0; i < n; i++) { parent[i] = -1; cycle[i] = -1; visit[i] = 0; count = 1; min = 10000; } } static boolean dfs (int x) { visit[x] = 1; for (int i = 0; i < n; i++) { if (matrix[x][i] != 0) { if (visit[i] == 0) { parent[i] = x; if (dfs(i)) return true; } else if (i != parent[x]) { start = i; end = x; return true; } } } return false; } static void checkMin() { for (int i = 0; i < count; i++) { int a, b; int tmp; if (i == count-1) { a = cycle[i]; b = cycle[0]; tmp = arr[i] + arr[0]; } else { a = cycle[i]; b = cycle[i+1]; tmp = arr[i] + arr[i+1]; } if (tmp < min) { min = tmp; x = a; y = b; } } sum += min; } static void removeEdge() { matrix[x][y] = matrix[y][x] = 0; } static void checkCycle() { if (dfs(0)) { int k = 0; cycle[k] = start; while (start != end) { for (int i = 0; i < n; i++) { if (parent[i] == start) { start = i; cycle[++k] = start; count++; } } } checkMin(); removeEdge(); } } static int count; static int [] parent; static int [] cycle; static int start; static int end; static int x, y; public static void main(String[] args) throws Exception { System.setIn(new FileInputStream("F:\\eclipse\\SRV\\src\\Tan_Cong_Thanh_Tri\\thanhtri.txt")); Scanner sc = new Scanner(System.in); int T = sc.nextInt(); for (int testcase = 1; testcase <= T; testcase++) { n = sc.nextInt(); matrix = new int [n][n]; visit = new int [n]; arr = new int [n]; parent = new int [n]; cycle = new int [n]; for (int i = 0; i < n; i++) { int num = sc.nextInt(); int a = sc.nextInt(); arr[num] = a; int b = sc.nextInt(); for (int j = 0; j < b; j++) { int c = sc.nextInt(); matrix[i][c] = 1; } } sum = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (matrix[i][j] == 1) { reset(); checkCycle(); } } } System.out.println(sum); } sc.close(); } }
Editor is loading...