Untitled
unknown
plain_text
a year ago
2.5 kB
5
Indexable
#1 176 #2 85 #3 80 #4 154 #5 3 #6 189 #7 99 #8 97 #9 209 #10 200 #11 79 #12 1 #13 197 #14 185 #15 23 #16 87 #17 29 #18 11 #19 140 #20 78 #21 211 #22 221 #23 120 #24 61 #25 91 #26 514 #27 180 #28 300 #29 165 #30 92 #31 165 #32 159 #33 173 #34 514 #35 628 #36 261 #37 171 #38 230 #39 55 #40 362 #41 26 #42 361 #43 122 #44 126 #45 465 #46 259 #47 72 #48 332 #49 280 #50 236 import java.util.Scanner; public class Solution { int N, M; int Answer; int Package[][]; int Value[]; int visit[]; int Subset[]; int SLM; int min; public static void main(String[] args) throws Exception { new Solution().begin(); } private void begin() throws Exception { Scanner sc = new Scanner(System.in); int T = sc.nextInt(); for (int test_case = 1; test_case <= T; test_case++) { Answer = 0; N = sc.nextInt(); Package = new int[51][51]; Value = new int[51]; min = 100000000; for (int i = 1; i <= N; i++) { for (int j = 1; j <= N; j++) { if (i == j) { Package[i][j] = 1; Value[i] = sc.nextInt(); } } } M = sc.nextInt(); for (int i = N + 1; i <= M + N; i++) { Value[i] = sc.nextInt(); int sl = sc.nextInt(); for (int j = 0; j < sl; j++) { int index = sc.nextInt(); Package[i][index] = 1; } } SLM = sc.nextInt(); visit = new int[N + 1]; for (int i = 0; i < SLM; i++) { int index = sc.nextInt(); visit[index] = 1; } Subset = new int[N + M + 1]; back(1, 0, visit); System.out.println("#" + test_case + " " + min); } } private void back(int i, int gia, int mua[]) { if (muaxong(mua)) { if (gia < min) { min = gia; Answer = gia; } return; } if (i == N + M + 1) { return; } if (check(i, gia)) { Subset[i] = 1; int temp[] = new int[N + 1]; for (int j = 1; j <= N; j++) { temp[j] = mua[j]; if (Package[i][j] == 1) { temp[j] = 0; } } back(i + 1, gia + Value[i], temp); } Subset[i] = 0; back(i + 1, gia, mua); } private boolean muaxong(int vs[]) { for (int i = 1; i <= N; i++) { if (vs[i] == 1) { return false; } } return true; } private boolean check(int j, int gia) { if (gia + Value[j] >= min) return false; for (int i = 1; i <= N; i++) { if (Package[j][i] == 1 && visit[i] == 1) { return true; } } return false; } }
Editor is loading...
Leave a Comment