Untitled
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