邮局（深搜+剪枝）

题目如下：

问题描述
　　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。

这道题使用的方法是剪枝+深搜。
解题步骤在于：
先设定一个邮局是已确定的，得出所有的村民到该邮局的距离。
再逐个进行判断未确定的邮局，如果该邮局到所有村民家的距离都大于当前最小值，那么该邮局被剪枝，即被放弃。
直到找遍所有的邮局且邮局数目为当前数目。
使用方法深搜则在于，每当确定一个邮局，那么下一个参数的传递值则加一，来标记已确定邮局数目。
其中需要注意到的是，从大到小首先确定一个数，然后从大到小依次判断是否可留，如果是，那么替换当前已确定最小数，否则，被剪枝。继续迭代。

#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)
{
    if (i <= m + 1)//如果还没有遍历完所有的邮局
    {
        if (t == k)//如果已经确定的邮局数已足够
        {
            if (sum<s)
            {
                s = sum;//s是最后的最小距离总值
                for (j = 0; j<k; j++)
                    d[j] = o[j];//将数组o的k个值存入数组d
            }
        }
        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); f1 = 1, f2 = 0;//下一个邮局，初始化两个标记用的变量f1，f2
            if (!f[i])//f[i]==0,还没有被剪掉
            {
                o[t] = i;//第t个已确定邮局是i
                if (t>0)//ww初始化已经
                {
                    f2 = 1;
                    for (j = 1; j <= n; j++)
                    {
                        if (ww[j]>yc[i][j])//如果邮局到村民家的距离小于当前最小
                        {
                            sum = sum - ww[j] + yc[i][j];//更新
                            ww[j] = yc[i][j];
                            f1 = 0;//变化，不剪掉当前邮局
                        }
                    }
                }
                else//还没有初始化
                {
                    for (j = 1; j <= n; j++)
                    {
                        sum += yc[i][j];
                        ww[j] = w[j] = yc[i][j];//初始化最小值就是当前值
                    }
                } 
                if (f1&&f2)//已经有过ww初始化且需要剪掉当前的邮局，ww如果未初始化那么一定不能剪掉
                {
                    f[i] = 1;//经过处理，已经被剪掉
                    dfs(t, i + 1, o, w, sum);//下一次迭代t不增加
                }
                else
                    dfs(t + 1, i + 1, o, ww, sum);//下一次迭代
            }
        }
    }
}
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]));
    }//yc[i][j]代表第i个邮局到第j个村民家的距离
    dfs(0, 1, o, w, 0);
    for (i = 0; i<k; i++)
        cout << d[i] << " ";
    return 0;
}