zzulioj--1730--通信基站（全排列+dfs）（好题）

1730: 通信基站

Time Limit: 1 Sec  Memory Limit:
128 MB

Submit: 28  Solved: 11



SubmitStatusWeb
Board

Description

Input

Output

Sample Input

2

2 1 1

0 0

4 4

3 100 1

0 0

1 1

500 500

Sample Output

2.00

201.41

原题链接

这次真是学到了，看得大神的代码，思路真是不错，最也就八个点，每个点有建与不建两种状态，所以最都也就是2^8种情况，我们每次列举有多少个地点建基站，然后就进行全排列，直到所有的全排列都列举一遍，prev_permutation（s+1，s+n+1）记录所有的全排列，然后再进行搜索，dfs查找出当前方案下最小的花费，搜索的时候要进行回溯

#include<cstdio>

#include<cstring>

#include<cmath>

#include<iostream>

#include<algorithm>

using namespace std;

#define INF 0x3f3f3f3f

int a[100],b[100];

int ta,tb;

double x[11],y[11];

double used[100],sum;

double Cr,Cs;

int n,s[100];

double dis(int a,int b)

{

	return sqrt((x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]));

}

void dfs(int pos)//pos记录已经覆盖的没有基站的数量

{

	if(pos==ta+1)

	{

		double res=0;

		for(int i=1;i<=n;i++)

		res+=used[i];

		sum=min(res,sum);//sum表示当前方案下最小的距离

		return ;

	}

	for(int j=1;j<=tb;j++)

	{

		double d=dis(b[j],a[pos]);

		double val=used[j];

		used[j]=max(used[j],d);//要用max，因为必须多个点全部覆盖

		dfs(pos+1);

		used[j]=val;//这个点可以不进行扩张

	}

}

double solve(int cnt)

{

	double res=Cs*cnt;

	ta=tb=0;

	for(int i=1;i<=n;i++)

	{

		if(s[i]) b[++tb]=i;

		else a[++ta]=i;

		used[i]=0;

	}

	sum=0;

	if(cnt!=n)

	sum=INF;//如果每个点都建立基站，sum就无意义

	dfs(1);//共有ta个点没有基站，所以其他基站要进行覆盖

	return res+sum*Cr;

}

int main()

{

	int t;

	scanf("%d",&t);

	while(t--)

	{

		scanf("%d%lf%lf",&n,&Cs,&Cr);

		for(int i=1;i<=n;i++)

		scanf("%lf%lf",&x[i],&y[i]);

		double ans=INF;

		for(int i=1;i<=n;i++)

		{

			memset(s,0,sizeof(s));

			for(int j=1;j<=i;j++)

			s[j]=1;

			do

			{

				ans=min(ans,solve(i));

			}while(prev_permutation(s+1,s+n+1));//判断是否已经完成所有的全排列

		}

		printf("%.2f\n",ans);

	}

	return 0;

}