历届试题 邮局
时间限制：1.0s 内存限制：256.0MB
问题描述
C村住着n户村民，由于交通闭塞，C村的村民只能通过信件与外界交流。为了方便村民们发信，C村打算在C村建设k个邮局，这样每户村民可以去离自己家最近的邮局发信。
现在给出了m个备选的邮局，请从中选出k个来，使得村民到自己家最近的邮局的距离和最小。其中两点之间的距离定义为两点之间的直线距离。
现在给出了m个备选的邮局，请从中选出k个来，使得村民到自己家最近的邮局的距离和最小。其中两点之间的距离定义为两点之间的直线距离。
输入格式
输入的第一行包含三个整数n, m, k，分别表示村民的户数、备选的邮局数和要建的邮局数。
接下来n行，每行两个整数x, y，依次表示每户村民家的坐标。
接下来m行，每行包含两个整数x, y，依次表示每个备选邮局的坐标。
在输入中，村民和村民、村民和邮局、邮局和邮局的坐标可能相同，但你应把它们看成不同的村民或邮局。
接下来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
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；
对于60%的数据，1<=m<=20；
对于100%的数据，1<=n<=50，1<=m<=25，1<=k<=10。
感觉这道题还是很不错的，刚开始没怎么看数据量，写的代码超时了
超时思路：m个备用邮局，建k个，如果用1,0表示建跟不建，那么数组中就有k个1，m-k个0，所以全排列之后就是每一个方案，然后计算出每一组方案的话费，之后取最优花费，但是有的数据比较大，比如50，如果有10个邮局，那么方案就有很多很多，组合数公式算下来肯定崩，但是这个思路对于小的数据应该还是可以的，先上超时代码：
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define INF 0x3f3f3f3f
struct node
{
double x,y;
}a[60],b[60];
int n,m,k,s[60],num[60];
double dis(int x,int y)
{
return sqrt((a[x].x-b[y].x)*(a[x].x-b[y].x)+(a[x].y-b[y].y)*(a[x].y-b[y].y));
}
double dfs()
{
double sum=0;
for(int i=0;i<n;i++)
{
double val=INF;
for(int j=0;j<m;j++)
{
if(s[j])
{
double d=dis(i,j);
val=min(val,d);
}
}
sum+=val;
}
return sum;
}
int main()
{
while(cin>>n>>m>>k)
{
memset(s,0,sizeof(s));
for(int i=0;i<n;i++)
cin>>a[i].x>>a[i].y;
for(int i=0;i<m;i++)
cin>>b[i].x>>b[i].y;
for(int i=0;i<k;i++)
s[i]=1;
int cnt;
double ans=INF;
do{
double si=dfs();
if(ans>si)
{
ans=si;
memset(num,0,sizeof(num));
cnt=0;
for(int i=0;i<m;i++)
if(s[i])
num[cnt++]=i;
}
}while(prev_permutation(s,s+m));
for(int i=0;i<k-1;i++)
printf("%d ",num[i]+1);
printf("%d
",num[k-1]+1);
}
return 0;
}</pre>AC思路（dfs+剪枝）：dfs最重要的就是建立搜索树，这里每个点都有两种状态，如果直接暴力时间肯定很长，所以需要加上剪枝，我们可以将村子的住户还有备用邮局看作是两个集合，就像普利姆的思路一样，总的思路就是更新最短距离数组，我们先将所有的点全部连接在第一个备用邮局，也可以不连第一个，毕竟每个点有两种状态，如果第二个备用邮局到住户的距离足以更新最短距离数组，那就更新之后寻找下一个邮局，如果不足以更新最短距离数组，我们就直接放弃这个点，显然他是没有用的，找到k个邮局之后就判定一下话费，是否更短，如果是，更新序号数组
#include<iostream>
#include<stdlib.h>
#include<math.h>
using namespace std;
int n,m,k,j,c[55][2],y[27][2],d[12],f1,f2,f[55]={0};
float yc[27][55],s=1000000000;
int dfs(int t,int i,int o[12],float w[55],float sum)
{//t±íʾѰÕҵĵÚi¸öÓʾ֣¬t±íʾ±¸ÓÃÓʾֵıàºÅ
if(i<=m+1)
{
if(t==k)//ÕÒµ½ÁËk¸öÓʾ֣¬²¢ÇÒÏûºÄ¸üµÍ
{
if(sum<s)
{
s=sum;
for(j=0;j<k;j++)
d[j]=o[j];
}
}
else if(i<=m&&t<k)
{
float ww[55];//´æ´¢×î¶Ì¾àÀë
for(j=1;j<=n;j++)
ww[j]=w[j];//×î¶Ì¾àÀ븴ÖÆ£¬Ã¿Ò»²½¶¼Òª½øÐÐ
dfs(t,i+1,o,w,sum);//Ò»¸öµãÓÐÁ½ÖÖ״̬£¬Õâ¸öÊDz»½¨Óʾֵģ¬
//½øÐÐÁËÕâÒ»²½£¬i²»²ÎÓë¸üÐÂ
f1=1,f2=0;//ÅжÏiÊÇ·ñ¿ÉÒÔʹÓÃ
if(!f[i])
{
o[t]=i;
if(t>0)
{
f2=1;//Èç¹ûi²»ÊǵÚ0¸öµã
for(j=1;j<=n;j++)
{
if(ww[j]>yc[i][j])
{
sum=sum-ww[j]+yc[i][j];//sum´¢´æ×ܵľàÀë
ww[j]=yc[i][j];
f1=0;//ww±»¸üеıê¼Ç
}
}
}
else
{
for(j=1;j<=n;j++)
{
sum+=yc[i][j];//¸Õ¿ªÊ¼Ê±È«²¿Á¬ÔÚµÚ1¸öµã¡£Ö®ºó¸üÐÂ
ww[j]=w[j]=yc[i][j];
}
}
if(f1&&f2)//¼ôÖ¦
{
f[i]=1;//²»ÊǵÚ0¸öµãÇÒ²»ÄܲÎÓë¸üÐÂ
dfs(t,i+1,o,w,sum);//Èç¹ûµÚi¸öÓʾֵ½ÆäËûn¸öµãµÄ¾àÀ붼±ÈwwÖеĴó£¬iÉáÆú
}
else
dfs(t+1,i+1,o,ww,sum);//µÚi¸öµã¿ÉÒÔ¸üÐÂww¾ÍʹÓøõã
}
}
}
}
int main()
{
int i,j,o[12];
float w[55],ww[55];
cin>>n>>m>>k;
for(i=1;i<=n;i++)
cin>>c[i][0]>>c[i][1];
for(i=1;i<=m;i++)
{
cin>>y[i][0]>>y[i][1];
for(j=1;j<=n;j++)
yc[i][j]=sqrt((c[j][0]-y[i][0])*(c[j][0]-y[i][0])+(c[j][1]-y[i][1])*(c[j][1]-y[i][1]));
}
dfs(0,1,o,w,0);
for(i=0;i<k;i++)
cout<<d[i]<<" ";
return 0;
}