Untitled
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...