蓝桥杯真题-邮局
#include<iostream>
#include<algorithm>
#include<set>
#include<string>
#include<cstring>
#include<vector>
#include<cmath>
using namespace std;
const double inf = 1.7e300;
struct node
{
int x, y;
}point[55], post[30];
double mp[55][55];
int flag[55];
int n, m, k;
double res = inf;
int cur[55];
int ans[55];
double dis(node a, node b)
{
return sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y));
}
//st表示当前考虑的邮局编号，sum_k表示的是已经加入的post总数，tmp_r[]表示
void dfs(int st, int sum_k, double sum_r, double tmp_r[])
{
if ((k - (sum_k-1)) > (m - (st-1))) return;//剪枝 1:左边表示还需要加入的邮局，右边表示剩余的邮局，邮局数量不够
if (st > m && sum_k <= k) return; //剪枝 2：已经没有剩余的邮局了，并且k个邮局还未加满
// if (sum_k > k+1) return;
if (sum_k == k+1)
{
//cout <<" shuchu" << st-1 << " " << sum_k-1 << " " << sum_r << endl;
if (res > sum_r)
{
res = sum_r;//更新，保存每一个邮局的编号
for (int i = 1; i <= k; i++)
{
ans[i] = cur[i];
}
}
return;
}
double dis_r[55];//必须重新定义一个数组才属于这个函数
for (int i = 1; i <= n; i++)
{
dis_r[i] = tmp_r[i];
}
dfs(st + 1, sum_k, sum_r, dis_r);//不建造此邮局
if (flag[st] == 1) return;//表示当前位置的邮局对于缩短距离没有增益，直接return,不需要考虑选择该邮局地点的方案
//下面表示加入当前邮局的情况
cur[sum_k] = st;//加入
int mark1 = 0, mark2 = 0;
if (sum_k ==1)//第一个邮局，初始化 dis_r
{
for (int i = 1; i <= n; i++)
{
dis_r[i] = mp[i][st];
sum_r += mp[i][st];
}
mark1 = 1;
}
else
{
for (int i = 1; i <= n; i++)
{
if (dis_r[i] > mp[i][st])
{
mark2 = 1;
sum_r += mp[i][st] - dis_r[i];
dis_r[i] = mp[i][st];
}
}
}
if (mark1 == 0 && mark2 == 0) flag[st] = 1;
if (mark1 == 1 || mark2 == 1) dfs(st + 1, sum_k + 1, sum_r, dis_r);
return;
}
void init()
{
for (int i = 1; i <= n; i++)
{
scanf("%d %d", &point[i].x, &point[i].y);
}
for (int i = 1; i <= m; i++)
{
scanf("%d %d", &post[i].x, &post[i].y);
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
mp[i][j] = dis(point[i], post[j]);
}
}
}
int main()
{
scanf("%d %d %d", &n, &m, &k);
init();
double dis_r[55];
memset(dis_r, -1, sizeof(dis_r));
dfs(1, 1, 0, dis_r);
for (int i = 1; i <= k; i++)
{
cout << ans[i] << " ";
}
return 0;
}