Q

用户名：Ryan228155

访问量：3014

签　名：

等　　级
排　　名	9367
经　　验	1161
参赛次数	0
文章发表	3
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

蓝桥杯历届试题-车轮轴迹-题解(C++代码)
浏览：1136

蓝桥杯历届试题-邮局-题解(C++代码)
浏览：1271

你可能喜欢

2006年春浙江省计算机等级考试二级C 编程题(2) （C++代码）直接打表啊8以上值不变hhh

蓝桥杯历届试题-邮局-题解(C++代码)

　　作者: Q　　　　发表时间：2020-02-24 14:25:43 浏览：1271　|　评论：0　

原题链接：蓝桥杯历届试题-邮局

请参考
```cpp
#include <bits/stdc++.h>
using namespace std;
 
const double inf = 1.7e300;
 
struct node
{
	int x, y;
}point[100], post[100];
 
double mp[101][101];
int flag[100];
int n, m, k;
double res = inf;
int cur[100];
int ans[100];
 
 
double dis(node a, node b)
{
	return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
}
 
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
	if(sum_k > k+1) return ;
	//cout << st-1 << " " <<  sum_k-1 << " " << sum_r << endl;
	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];
			}
			//cout << "   " << res << endl;
		}
		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 ;
	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;
 }
```

0.0分

6 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

Q

TA的其他文章

你可能喜欢

人民币问题（C语言代码）

C语言程序设计教程（第三版）课后习题7.4 （C++代码）

2006年春浙江省计算机等级考试二级C 编程题(2) （C++代码）直接打表啊8以上值不变hhh

C语言程序设计教程（第三版）课后习题7.4 （C语言代码）

矩形面积交（C语言代码）

蓝桥杯历届试题-邮局-题解(C++代码)

评论区

精彩推荐

汽水瓶（C语言代码）

C语言程序设计教程（第三版）课后习题8.3 （Java代码）

大神老白（C语言代码）

奖学金（C++代码）

买不到的数目（C++代码）

回文串（C语言代码）

简单的a+b （C语言代码）

【亲和数】（C语言代码）

C语言训练-大、小写问题（C语言代码）

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

Q

TA的其他文章

你可能喜欢

人民币问题 （C语言代码）

C语言程序设计教程（第三版）课后习题7.4 （C++代码）

2006年春浙江省计算机等级考试二级C 编程题(2) （C++代码）直接打表啊8以上值不变hhh

C语言程序设计教程（第三版）课后习题7.4 （C语言代码）

矩形面积交 （C语言代码）

蓝桥杯历届试题-邮局-题解(C++代码)

评论区

精彩推荐

汽水瓶 （C语言代码）

C语言程序设计教程（第三版）课后习题8.3 （Java代码）

大神老白 （C语言代码）

奖学金 （C++代码）

买不到的数目 （C++代码）

回文串 （C语言代码）

简单的a+b （C语言代码）

【亲和数】 （C语言代码）

C语言训练-大、小写问题 （C语言代码）

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

人民币问题（C语言代码）

矩形面积交（C语言代码）

　　评论区

汽水瓶（C语言代码）

大神老白（C语言代码）

奖学金（C++代码）

买不到的数目（C++代码）

回文串（C语言代码）

【亲和数】（C语言代码）

C语言训练-大、小写问题（C语言代码）