Untitled

mail@pastecode.io avatar
unknown
plain_text
2 years ago
2.7 kB
2
Indexable
package Nang_Cap_May_Tinh;

import java.io.FileInputStream;
import java.util.Scanner;

public class nang_cap_may_tinh {
	static int n, m, l, Ans;
	static int [] giaTroi, Kim, visit;
	static int [][] sale;
	
	//dem so linh kien cua goi sale x
	static int countSale(int x) {
		if (x == m + n) return 0;
		
		int count = 0;
		for (int i = 2; i < sale[x][1] + 2; i++) {
			 if(visit[sale[x][i]] == 0) {
				 count++;
				 visit[sale[x][i]]++;
			 }
		}
		return count;
	}
	
	//check visit
	static void check(int x) {
		for (int i = 2; i < sale[x][1] + 2; i++) {
			 if(visit[sale[x][i]] == 0) {
				 visit[sale[x][i]]++;
			 }
		}
	}
	
	//check visit
		static void uncheck(int x) {
			for (int i = 2; i < sale[x][1] + 2; i++) {
				 if(visit[sale[x][i]] > 0) {
					 visit[sale[x][i]]--;
				 }
			}
		}
		
		static void reset() {
			for (int i = 0; i < n+1; i++) {
				visit[i] = -1;
			}
			for (int i = 0; i < l; i++) {
				visit[Kim[i]] = 0;
			}
		}
	static void Try(int x, int sumCost, int count) {
		if (x == m + n + 1) {
			return;
		}
		if (Ans < sumCost) return;
		if (count == l) {
			if (Ans > sumCost) Ans = sumCost;
			return;
		}
		
		
		int num = countSale(x);
		
		if(num > 0) {
			//mua linh kien
//			check(x);
			Try(x+1, sumCost + sale[x][0], count + num);
			uncheck(x);
			
			// khong mua linh kien
			Try(x+1, sumCost, count);
		} else {
			Try(x+1, sumCost, count);
		}
		
	}
	
	
	public static void main(String[] args) throws Exception{
		System.setIn(new FileInputStream("F://eclipse//SRV//src//Nang_Cap_May_Tinh//may_tinh.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int test_case = 1; test_case <= T; test_case++) {
			// input gia tung linh kien
			n = sc.nextInt();
			giaTroi = new int[n];
			visit = new int[n+1];
			for (int i = 0; i < n; i++) {
				giaTroi[i] = sc.nextInt();
			}
			// input cac goi sale
			m = sc.nextInt();
			sale = new int [m+n][n+2];
			for (int i = 0; i < m; i++) {
				// cot dau tien la gia cua goi sale
				sale[i][0] = sc.nextInt();
				sale[i][1] = sc.nextInt();
				for (int j = 2; j < sale[i][1] + 2; j++) {
					sale[i][j] = sc.nextInt();
				}
			}
			// input cac linh kien Kim can mua
			l = sc.nextInt();
			Kim = new int[l];
			for (int i = 0; i < l; i++) {
				Kim[i] = sc.nextInt();
//				visit[Kim[i]] = -1;
			}
			
			for (int i = m; i < m+n; i++) {
				sale[i][0] = giaTroi[i-m];
				sale[i][1] = 1;
				sale[i][2] = i-m+1;
			}
			reset();
			
			Ans = 100000;
			Try(0, 0, 0);
			
			System.out.println(Ans);
		}

	}

}