Untitled

 avatar
unknown
plain_text
2 years ago
2.4 kB
6
Indexable
package piza;

import java.util.Scanner;

public class test {
static int K,R;
static int num_ToaDoDi;
static int num_ToaDoDen;
static int[][] ToaDoDi=new int[100][2];
static int[][] ToaDoDen=new int[100][3];
static int[] vsdi=new int[100];
static int[] vsden=new int[100];
static int[][] matrix=new int[100][100];
static int ans=0;
static int count=0;
static int[] sodiemgiao=new int[100];
static boolean checkKC(int x1,int y1,int x2,int y2){
	if ((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2) <= R*R) {
		return true;
	} 
	return false;
}
static void reset(){
	for(int j=0;j<100;j++){
		vsdi[j]=0;
		vsden[j]=0;
		sodiemgiao[j]=0;
	}
	
}
static void backtrack(int k,int sum,int id){
	if(k==K){
		if(sum>ans){
			ans=sum;
		}
		return;
	}
	for(int i=id;i<num_ToaDoDi;i++){
		if(vsdi[i]==0){
			vsdi[i]=1;
			int t=0;
			for(int j=0;j<sodiemgiao[i];j++){
				if(vsden[matrix[i][j]]==0){
					t+=ToaDoDen[matrix[i][j]][2];
				}
				vsden[matrix[i][j]]++;
			}
			backtrack(k+1, sum+t, i);
			vsdi[i]=0;
			
			for(int j=0;j<sodiemgiao[i];j++){
				
				vsden[matrix[i][j]]--;
			}
		}
	}
}
public static void main(String[] args) {
	Scanner scanner=new Scanner(System.in);
	int tc=scanner.nextInt();
	for(int i=0;i<tc;i++){
		reset();
		K=scanner.nextInt();
		R=scanner.nextInt();
		num_ToaDoDi=scanner.nextInt();
		for(int j=0;j<num_ToaDoDi;j++){
			for(int k=0;k<2;k++){
				ToaDoDi[j][k]=0;
			}
		}
		for(int j=0;j<num_ToaDoDi;j++){
			ToaDoDi[j][0]=scanner.nextInt();
			ToaDoDi[j][1]=scanner.nextInt();
		}
		num_ToaDoDen=scanner.nextInt();
		for(int j=0;j<num_ToaDoDen;j++){
			for(int k=0;k<3;k++){
				ToaDoDen[j][k]=0;
			}
		}
		for(int j=0;j<num_ToaDoDen;j++){
			ToaDoDen[j][0]=scanner.nextInt();
			ToaDoDen[j][1]=scanner.nextInt();
			ToaDoDen[j][2]=scanner.nextInt();
		}
		for(int j=0;j<num_ToaDoDi;j++){
			for(int k=0;k<num_ToaDoDen;k++){
				matrix[j][k]=0;
			}
			
		}
		
		for(int j=0;j<num_ToaDoDi;j++){
			for(int k=0;k<num_ToaDoDen;k++){
				if(checkKC(ToaDoDi[j][0], ToaDoDi[j][1], ToaDoDen[k][0],ToaDoDen[k][1])){
					matrix[j][sodiemgiao[j]++]=k;
				}
			}
		}
//		for(int j=0;j<num_ToaDoDi;j++){
//			for(int k=0;k<num_ToaDoDen;k++){
//				System.out.print(matrix[j][k]+" ");
//			}
//			System.out.println();
//		}
		
		ans=0;
		backtrack(0, 0,0);
		System.out.println("#"+(i+1)+" "+ans);
	}
}
}
Editor is loading...