Untitled
unknown
plain_text
a month ago
2.2 kB
1
Indexable
Never
package backtrack; import java.io.FileInputStream; import java.io.FileNotFoundException; import java.util.Scanner; public class upgradePC { static int n; static int price[]; static int arr[][]; static int buy[]; static int total; static int min; static int check[]; static int numbuy; static int ud; static boolean checkBuy() { for (int i = 0; i < numbuy; i++) { if (check[buy[i]] == 0) { return false; } } return true; } static int sumBuy() { int c = total; for (int i = 0; i < numbuy; i++) { if (check[buy[i]] == 0) { c += price[buy[i]]; } } return c; } static void backtrack(int v) { if (total > min) { return; } if (v == ud ) { if (checkBuy()) { if (total < min) { min = total; } } else { if (sumBuy() < min) { min = sumBuy(); } } return; } for (int i = 0; i < 2; i++) { if (i == 0) { total += arr[v][0]; for (int j = 0; j < arr[v][1]; j++) { check[arr[v][j + 2]]++; } backtrack(v + 1); total -= arr[v][0]; for (int j = 0; j < arr[v][1]; j++) { check[arr[v][j + 2]]--; } } else { backtrack(v + 1); } } } public static void main(String[] args) throws FileNotFoundException { System.setIn(new FileInputStream("Text")); Scanner scanner = new Scanner(System.in); int tc = scanner.nextInt(); for (int Case = 1; Case <= tc; Case++) { n = scanner.nextInt(); price = new int[n + 1]; for (int i = 1; i <= n; i++) { price[i] = scanner.nextInt(); } ud = scanner.nextInt(); arr = new int[ud][n + 1]; for (int i = 0; i < ud; i++) { arr[i][0] = scanner.nextInt(); arr[i][1] = scanner.nextInt(); for (int j = 0; j < arr[i][1]; j++) { arr[i][j + 2] = scanner.nextInt(); } } numbuy = scanner.nextInt(); buy = new int[numbuy]; for (int i = 0; i < numbuy; i++) { buy[i] = scanner.nextInt(); } check = new int[n+1]; total = 0;` min = Integer.MAX_VALUE; backtrack(0); System.out.println("#"+ Case+" "+ min); } } }