[藍橋杯][曆屆試題]郵局

題目

添加連結描述

題解

dfs+剪枝。

剪不出來，45%。看做出來的網上的題解也少，還看不懂。

就先這樣吧。

有大佬會的話可以評論一下，請教一下。

代碼

#include<bits/stdc++.h>
using namespace std;
const int N = 100;

struct node{
	double x, y;
}a[N], b[N];

double ans = 1e18, dis[N][N], minpath;
int vis[N], op[N], out[N], n, m, k;

void dfs(int x, int step) {
	
	if(step>k) {
		double res = 0;
		
		for(int i = 1;i <= n;i ++) {
			minpath =  dis[op[1]][i];
			for(int j = 2;j <= k;j ++) minpath = min(minpath, dis[op[j]][i]);
			res += minpath;
			if(res >= ans) return ;
		}
		
		if(res < ans) {
			for(int i = 1;i <= k;i ++) out[i] = op[i];
			ans = res;
		}
		return ;
	} 
	
	for(int i = 1;i <= m;i ++) {
		if(vis[i]) continue;
		vis[i] = 1;
		op[step] = i;
		dfs(i, step+1);
		vis[i] = 0;
	}
}

int main()
{
	cin>>n>>m>>k;
	for(int i = 1;i <= n;i ++) cin>>a[i].x>>a[i].y;
	for(int i = 1;i <= m;i ++) cin>>b[i].x>>b[i].y;
	
	for(int i = 1;i <= m;i ++) 
	for(int j = 1;j <= n;j ++) 
	dis[i][j] = sqrt((b[i].x-a[j].x)*(b[i].x-a[j].x) + (b[i].y-a[j].y)*(b[i].y-a[j].y));
	
	dfs(0, 1);

	for(int i = 1;i <= k;i ++) cout << out[i] << ' ';
	return 0;
}