Untitled

 avatar
user_4230122
c_cpp
a year ago
2.0 kB
6
Indexable
#include <iostream>

using namespace std;
int t,n;
int giachotroi[21];
int m;
int giauudai[31];
int num_linhkien_uudai[21];
int linhkienuudai[21][21];
int l;
int lk_need[21];
int visit_lk_need[21];
int visit[31];

int min1;
void danhdau(int index) {
	for (int i = 1; i <= num_linhkien_uudai[index]; i++) {
		for (int j = 1; j <= l; j++) {
			if (linhkienuudai[index][i] == lk_need[j]) {
				visit_lk_need[j] = 1;
			}
		}
	}
}
void undanhdau(int index) {
	for (int i = 1; i <= num_linhkien_uudai[index]; i++) {
		for (int j = 1; j <= l; j++) {
			if (linhkienuudai[index][i] == lk_need[j]) {
				visit_lk_need[j] = 0;
			}
		}
	}
}
bool isFullLK() {
	for (int i = 1; i <= l; i++) {
		if (visit_lk_need[i] == 0)  return false;
	}
	return true;
}

// goi day giong step khi du 5 goi thi dung
void bt(int goi, int sum) {
	// dk dung
	if (sum > min1)  return;
	if (goi == l+1) {
		if (isFullLK()) {
			if (min1 > sum) {
				min1 = sum;
			}
			return;
		}
		else {
			for (int i = 1; i <= l; i++) {
				if (visit_lk_need[i] == 0) {
					sum += giachotroi[lk_need[i]];
				}
			}
			if (min1 > sum) {
				min1 = sum;
			}
			return;
		}
	}
	for (int i = 0; i <= 1; i++) {
		if (i == 0) {
			bt(goi + 1, sum);
		}
		else {
			visit[goi] = 1;
			danhdau(goi);
			bt(goi + 1, sum + giauudai[goi]);
			undanhdau(goi);
			visit[goi] = 0;
		}
	}
}
int main() {
	cin >> t;
	for (int tc = 0; tc < t; tc++) {
		cin >> n;
		for (int i = 1; i <= n; i++) {
			cin >> giachotroi[i];
			visit_lk_need[i] = 0;
		}
		cin >> m;
		for (int i = 1; i <= m; i++) {
			visit[i] = 0;
			cin >> giauudai[i] >> num_linhkien_uudai[i];
			for (int j = 1; j <= num_linhkien_uudai[i]; j++) {
				cin >> linhkienuudai[i][j];
			}
		}
		cin >> l;
		for (int i = 1; i <= l; i++) {
			cin >> lk_need[i];
		}
		min1 = 1000000;
		bt(1, 0);
		cout << "#" << tc + 1 << " " << min1 << endl;
	}
	return 0;
}
Editor is loading...
Leave a Comment