问题描述
C村住着n户村民，由于交通闭塞，C村的村民只能通过信件与外界交流。为了方便村民们发信，C村打算在C村建设k个邮局，这样每户村民可以去离自己家最近的邮局发信。
现在给出了m个备选的邮局，请从中选出k个来，使得村民到自己家最近的邮局的距离和最小。其中两点之间的距离定义为两点之间的直线距离。
输入格式
输入的第一行包含三个整数n, m, k，分别表示村民的户数、备选的邮局数和要建的邮局数。
接下来n行，每行两个整数x, y，依次表示每户村民家的坐标。
接下来m行，每行包含两个整数x, y，依次表示每个备选邮局的坐标。
在输入中，村民和村民、村民和邮局、邮局和邮局的坐标可能相同，但你应把它们看成不同的村民或邮局。
输出格式
输出一行，包含k个整数，从小到大依次表示你选择的备选邮局编号。（备选邮局按输入顺序由1到m编号）
样例输入
5 4 2
0 0
2 0
3 1
3 3
1 1
0 1
1 0
2 1
3 2
样例输出
2 4
数据规模和约定
对于30%的数据，1<=n<=10，1<=m<=10，1<=k<=5；
对于60%的数据，1<=m<=20；
对于100%的数据，1<=n<=50，1<=m<=25，1<=k<=10。
其实没有想象中的那么难，慢慢做还是能得部分分的。测不过的是精度丢失。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
| import java.util.Scanner;
public class 邮局 {
static double[][] dp;
static int[] arr;
static boolean[] vis;
static double ans=Integer.MAX_VALUE;
static int[] out;
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int m=sc.nextInt();
int k=sc.nextInt();
int[][] cun=new int[n][2];
for (int i = 0; i < cun.length; i++) {
int x=sc.nextInt();
int y=sc.nextInt();
cun[i][0]=x;
cun[i][1]=y;
}
int[][] youju=new int[m][2];
for (int i = 0; i < youju.length; i++) {
int x=sc.nextInt();
int y=sc.nextInt();
youju[i][0]=x;
youju[i][1]=y;
}
dp=new double[m][n];
for (int i = 0; i < youju.length; i++) {
for (int j = 0; j < cun.length; j++) {
int h=youju[i][0]-cun[j][0];
int w=youju[i][1]-cun[j][1];
double l=Math.pow(Math.abs(w*w+h*h),0.5);
dp[i][j]=l;
}
}
arr=new int[k];
out=new int[k];
vis=new boolean[m];
dfs(arr,0,m,-1);
for (int i = 0; i < out.length; i++) {
System.out.print(out[i]+" ");
}
}
private static void dfs(int[] arr, int i, int m,int t) {
if(i==arr.length){
double sum=0;
for (int j = 0; j < dp.length; j++) {
//竖着最小值
double min=Integer.MAX_VALUE;
for (int k = 0; k < arr.length; k++) {
if(dp[arr[k]-1][j]<min){
min=dp[arr[k]-1][j];
}
}
sum+=min;
}
if(sum<ans){
for (int j = 0; j < arr.length; j++) {
out[j]=arr[j];
}
ans=sum;
}
return;
}
for (int j = t+1; j < m; j++) {
if(!vis[j]){
arr[i]=j+1;
t=j;
vis[j]=true;
dfs(arr,i+1,m,t);
vis[j]=false;
}
}
}
}
|