问题描述 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: 当到第idx个邮局时，后面所有的邮局全选的情况仍不满足条件，可直接跳出。 剪枝2: 当第idx个邮局无法松弛距离，做一个标记，之后只走不标记的那条路。
#include <bits/stdc++.h> using namespace std; int x[105],y[105],xx[105],yy[105],n,m,k,vis[105]; double d[105][105],minn = 999999; //d[i][j]数组存储第i个邮局到第j户村民的距离 vector<int> res; void dfs(int arr[],int num,double sum,int idx){ if(num == k){ if(sum < minn){ minn = sum; res.clear(); for(int i = 0;i < k;i++){ res.push_back(arr[i]); } } return ; } if(idx >= m){ return ; } dfs(arr,num,sum,idx+1); if(vis[idx]) return ; arr[num] = idx; double tsum = 0,tsum2 = 0; for(int i = 0;i < n;i++){ double mm = 99999; for(int j = 0;j <= num;j++){ mm = min(mm,d[arr[j]][i]); } tsum += mm; for(int j = idx+1;j < m;j++){ mm = min(mm,d[j][i]); } tsum2 += mm; } //剪枝1 if(tsum2 > minn){ return ; } //剪枝2 if(tsum == sum){ vis[idx] = 1; } dfs(arr,num+1,tsum,idx+1); } int main(){ cin>>n>>m>>k; for(int i = 0;i < n;i++){ int a,b; cin>>a>>b; x[i] = a; y[i] = b; } for(int i = 0;i < m;i++){ int a,b; cin>>a>>b; xx[i] = a; yy[i] = b; } for(int i = 0;i < m;i++){ for(int j = 0;j < n;j++){ d[i][j] = sqrt((xx[i]-x[j])*(xx[i]-x[j])+(yy[i]-y[j])*(yy[i]-y[j])); } } int arr[105]; dfs(arr,0,99999,0); for(int i = 0;i < res.size();i++){ cout<<res[i]+1<<" "; } return 0; }