Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
2.5 kB
2
Indexable
Never
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();

	}

}