时间限制：1.0s   内存限制：256.0MB

    

问题描述

　　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。

感觉这道题还是很不错的，刚开始没怎么看数据量，写的代码超时了

超时思路：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\n",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;

}