Untitled

mail@pastecode.io avatar
unknown
plain_text
24 days ago
1.4 kB
2
Indexable
Never
#include<iostream>
using namespace std;
int t,k,r,m,n,ans;
int a,b,c;
int solita[100][3], loca[20][2], kc[20][100];
int vtsol[100];
bool vtloc[20];

int dis(int a){
	int b=0;
	for(int i=0; i<n; i++){
		if( vtsol[i]==-1 && kc[a][i] !=0){
			b+=kc[a][i];
			vtsol[i]=a;
		}
	}
	return b;
}

void bt(int dem, int current, int index){
	if(dem==k){
		if(current>ans)
			ans=current;
	}else if(index<m){
		if(vtloc[index]){
			vtloc[index]=false;
			int c=dis(index);
			current+=c;
			bt(dem+1,current,index+1);
			vtloc[index]=true;
			current-=c;
			for(int j=0; j<n; j++){
				if(vtsol[j]==index)
					vtsol[j]=-1;
			}
			bt(dem,current,index+1);
		}
	}
}

int main(){
	freopen("Text.txt", "r", stdin);
	cin >> t;
	for(int tc=1; tc<=t; tc++){
		cin >> k >> r;
		cin >> m;
		for(int i=0; i<m; i++){
			cin >> a >> b;
			loca[i][0]=a;
			loca[i][1]=b;
			vtloc[i]=true;
		}
		cin >> n;
		for(int i=0; i<n; i++){
			cin >> a >> b >> c;
			solita[i][0]=a;
			solita[i][1]=b;
			solita[i][2]=c;
			vtsol[i]=-1;
		}
		for(int i=0; i<m; i++){
			for(int j=0; j<n; j++){
				if(((loca[i][0]-solita[j][0])*(loca[i][0]-solita[j][0]) + (loca[i][1]-solita[j][1])*(loca[i][1]-solita[j][1])) <= r*r){
					kc[i][j]=solita[j][2];
				}else{
					kc[i][j]=0;
				}
			}
		}
		ans=0;
		bt(0,0,0);
		cout << "#" << tc << " " << ans << endl;
	}
	return 0;
}
Leave a Comment