Untitled

 avatar
unknown
plain_text
a year ago
1.8 kB
3
Indexable
#include<iostream>
using namespace std;
int a[30];
int gia[30];//gia cho troi
int giasale[30];//gia goi tuong ung voi goi
int sale[30][30];//i la so goi, j la so linh kien co trong
int countt[30];//so linh kien co trong moi goi
int can[30];//so linh kien can mua
int visited[30];//danh dau so linh kien can mua
int n, m;
int sum;
int maxx;
void backtrack(int u){
	if(u==m+1) return;
	for(int c=0; c<2; c++){
		bool ch=false;
		if(c==0){

		for(int i=1; i<countt[u]; i++){
			if(visited[sale[u][i]]==0){
				ch = true;
			}
		}
		if(ch==true){
			int a[30];
			int dem=0;

			for(int i=1; i<countt[u]; i++){
				if(visited[sale[u][i]]==0){
					visited[sale[u][i]]=1;
					a[dem]=sale[u][i];
					dem++;
				}
			}
			sum+=giasale[u];
			int e=sum;
			for(int i=1; i<=n; i++){
				if(visited[i]==0) sum+=gia[i];
			}
			if(sum<maxx) maxx=sum;
			sum = e;
			backtrack(u+1);
			sum-=giasale[u];
			for(int i=0; i<dem; i++){
				visited[a[i]]=0;
			}
		}
		
	}
	else backtrack(u+1);
	}
}
int main(){
	//freopen("in.txt", "r", stdin);
	int t;
	cin>>t;
	for(int tc=1; tc<=t; tc++){
		cin>>n;
		for(int i=1; i<=n; i++){
			cin>>gia[i];
			visited[i]=0;
		}
		cin>>m;
		for(int i=1; i<=m; i++) countt[i]=1;
		int x, y;
		for(int i=1; i<=m; i++){
			cin>>y;
			giasale[i]=y;
			cin>>x;
			for(int j=1; j<=x; j++){
				cin>>sale[i][countt[i]++];
			}
		}
		int p;
		cin>>p;
		for(int i=1; i<=p; i++) cin>>can[i];
		maxx=0;
		for(int i=1; i<=n; i++){
			int d=0;
			for(int j=1; j<=p; j++){
				if(i==can[j]){
					d++;
				}
			}
			if(d==0) visited[i]=1;
		}
		for(int i=1; i<=n; i++){
			if(visited[i]==0)
			maxx+=gia[i];
		}
		sum=0;
		backtrack(1);
		cout<<"#"<<tc<<" ";
		cout<<maxx<<endl;
	}
	return 0;
}