Untitled
unknown
plain_text
a year ago
1.8 kB
4
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; }
Editor is loading...