Untitled

mail@pastecode.io avatar
unknown
plain_text
9 days ago
2.5 kB
1
Indexable
Never
#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;
 }

}
Leave a Comment