问题描述 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.剪枝的地方有两点：剩余可选的点不够用的话就返回；当前的点如果没有被更新到的话，标记一下，以后也不用这个点了 还有别的细节的地方也要注意。
#include<cstdio> #include<cstring> #include<cmath> #include<iostream> #include<algorithm> #include<queue> #include<vector> #include<map> using namespace std; const int N=55; const int inf=0x3f3f3f3f; typedef long long ll; struct node{ int x,y; }s[N]; struct node1{ int x,y; double d[N]; }s1[N]; int m,k,n,vis[N]; double dis[N],mx=inf; vector<int>vex; void dfs(int pos,double sum,int num,vector<int>v){//分别为当前节点，总距离，已选点的个数，已选的点 if(num+(m-pos+1)<k) return;// 已选点的个数加上剩余的点不够k if(num==k){ if(sum<mx){ mx=sum; vex=v; } return; } dfs(pos+1,sum,num,v);//不选当前节点 if(vis[pos]) return; double temp[N]; memcpy(temp,dis,sizeof(temp));//把dis 的内容复制到temp中，temp不能是全局变量。。。 int flag=0; for(int i=1;i<=n;i++){//更新 if(dis[i]>s1[pos].d[i]){ dis[i]=s1[pos].d[i]; flag=1; } } sum=0; for(int i=1;i<=n;i++){ sum+=dis[i]; } if(flag){ v.push_back(pos); dfs(pos+1,sum,num+1,v); memcpy(dis,temp,sizeof(dis)); v.pop_back(); } else vis[pos]=1;//当前邮局没有被更新过，标记不可用 } int main() { int i,j; scanf("%d %d %d",&n,&m,&k); for(i=1;i<=n;i++){ scanf("%d %d",&s[i].x,&s[i].y); dis[i]=inf;//用memset更新double类型时，inf也应该weidouble类型 } for(i=1;i<=m;i++){ scanf("%d %d",&s1[i].x,&s1[i].y); for(j=1;j<=n;j++){ s1[i].d[j]=sqrt((s1[i].x-s[j].x)*(s1[i].x-s[j].x)+(s1[i].y-s[j].y)*(s1[i].y-s[j].y)); } } dfs(1,0,0,vex); sort(vex.begin(),vex.end()); for(i=0;i<vex.size();i++){ printf("%d ",vex[i]); } return 0; }