nangcapmaytinhc2

 avatar
duyvan
plain_text
19 days ago
2.4 kB
2
Indexable
Never
#include<iostream>

using namespace std;
//int LinhKien[21]; // mang luu gia linh kien
int SL; // so luong linh kien chinh
int SLuudai; // so luong uu dai
int UuDai[60][60];
int Slcanmua;
int Mua[40];
//int visit[20]= {0}; // check du so luong can mua
//int countt;
//int Vitri[60];
bool visit[60];
int Hang[60][60];
int A[60] = {};
int minx;

void xuat(){
	int ans = 0;

	for(int i = 1; i <= Slcanmua; i++){
		//cout<<A[i]<<" ";
		if(visit[A[i]-1] == -1){
			ans+=UuDai[A[i]-1][0];
		}
		visit[A[i]-1] = 1;
	}
	if(minx > ans) minx = ans;
	//cout<<ans<<endl;
}

int ans;
void sinh(int idx, int dodai, int sum){
	if(sum > ans) return;
	if(idx == Slcanmua+1){
		ans = min(ans, sum);
		return;
	}

	for(int i = 1; i < 1 + dodai; i++){
		A[idx] = Hang[Mua[idx-1]][i];
		if(visit[A[idx]] == false){
			visit[A[idx]] = true;
			sinh(idx+1, Hang[Mua[idx]][0], sum + UuDai[A[idx]-1][0]);
			visit[Hang[Mua[idx-1]][i]] = false;
		}
		else {
			sinh(idx+1, Hang[Mua[idx]][0], sum);
		}
	}
}


int main(){
	//freopen("input.txt", "r", stdin);
	//freopen("outputt.txt", "w", stdout);
	int T;
	cin>>T;

	for(int tc = 0; tc < T; tc++){
		cin>>SL;
		ans = 9999;
		for(int i = 0; i < 60;i++){
			visit[i] = 0;
		}
		for(int i = 0; i < 60; i++){
			for(int j = 0; j < 60; j++) {
				UuDai[i][j] = 0;
				Hang[i][j] = 0;
			}
		}
		for(int i = 0; i < SL; i++) {
			cin>>UuDai[i][0];
			UuDai[i][3] = i+1;
			UuDai[i][1] = 1;
		}
		cin>>SLuudai;
		for(int i = 0; i < SLuudai; i++){
			cin>>UuDai[i+SL][0]>>UuDai[i+SL][1];
			for(int j = 0; j < UuDai[i+SL][1]; j++){
				cin>>UuDai[i+SL][j+3];
			}
		}

		cin>>Slcanmua;
		//countt = 0;
		for(int i = 0; i < Slcanmua; i++) cin>>Mua[i];

		// Bai lam 
		//UuDai: UuDai[0]: Gia, UuDai[1]: SL trong hang, UuDai[2] ton tai linh kien can mua
		// UuDai[3,4,5...] ma linh kien
		for(int k = 0; k < Slcanmua; k++) 
		{
			int count = 1;
			int countt = 0;
			for(int i = 0; i < SLuudai+SL; i++) // check toan bo hang
			{
				for(int j = 0; j < UuDai[i][1]; j++) // check tren tung hang
				{

					if(UuDai[i][j+3] == Mua[k]) 
					{
						Hang[Mua[k]][count] = i+1;
						count++;
						//UuDai[i][2] = UuDai[i][j+3];
						countt++;
					}
				}

			}
			Hang[Mua[k]][0] = countt;
		}
		int cnt = 0;
		sinh(1, Hang[Mua[0]][0], 0);
		cout<<"#"<<tc+1<<" "<<ans<<endl;
	}
	return 0;
}
Leave a Comment