Nang_cap_may_tinh
unknown
plain_text
a year ago
2.4 kB
7
Indexable
Never
package Nang_Cap_May_Tinh; import java.io.FileInputStream; import java.util.Scanner; public class nang_cap_may_tinh { static int n, m, l; static int [] giaTroi, Kim, visit; static int [][] sale; static int Ans; // check cac linh kien can mua, danh dau vao visit, dem so luong linh kien da mua static int checkSale(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) { visit[sale[x][i]]++; count++; } } return count; } static void unVisit(int x) { for (int i = 2; i < sale[x][1] + 2; i++) { if(visit[sale[x][i]] > 0) { visit[sale[x][i]]--; } } } static void dfs(int x, int cost, int count) { if (Ans < cost) return; if (x == m + n + 1) return; if (count == l) { if (Ans > cost) Ans = cost; return; } int num = checkSale(x); if (num > 0) { //danhdau dfs(x+1, cost + sale[x][0], count + num); //tralai unVisit(x); } dfs(x+1, cost, count); } static void reset() { for (int i = 0; i < n+1; i++) { visit[i] = -1; } } public static void main(String[] args) throws Exception{ System.setIn(new FileInputStream("D://Trainee//SRV_training//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]; reset(); 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]] = 0; } for (int i = m; i < m+n; i++) { sale[i][0] = giaTroi[i-m]; sale[i][1] = 1; sale[i][2] = i - m + 1; } Ans = 100000; dfs(0, 0, 0); System.out.println("#" + test_case + " " + Ans); } } }