题目链接：https://acm.zzuli.edu.cn/zzuliacm/problem.php?id=1730
此题的关键就在于找到基站的辐射半径
枚举在呢些点建基电站，用一个全排列，1代表建，0代表不建。我们把0的点存为y[]，1的点存为x[]，然后就是从x[]里面选若干个点引半径做圆 来覆盖y[]里面的所有点，只需要求出最小半径和.
#include<stdio.h> #include<string.h> #include<algorithm> #include<math.h> #define INF 0x3f3f3f3f using namespace std; double a[10],b[10]; int vis[10],n; double Cs,Cr; int x[10],y[10]; double bj[10]; int s1,s2; double sum,minn; void dfs(int v) { if(v==s1+1)//已经把所有不建基站的地方都覆盖 { double cnt=0; for(int i=1; i<=s2; i++) cnt+=bj[i]; sum=min(sum,cnt); return; } for(int i=1; i<=s2; i++)//把s2个建基站的半径扩大来覆盖s1个不建基站的地方 { double dis=sqrt((a[x[i]]-a[y[v]])*(a[x[i]]-a[y[v]])+(b[x[i]]-b[y[v]])*(b[x[i]]-b[y[v]]));//半径 double ls=bj[i]; bj[i]=max(bj[i],dis);//注意，选最大的才能全部被覆盖 dfs(v+1); bj[i]=ls;//回溯，这个基站不向外扩展 } } void fun() { s1=0,s2=0; for(int i=1; i<=n; i++) { if(vis[i]==0) y[++s1]=i;//不建基站的放在y数组 else x[++s2]=i;//建基站的放在x数组 } if(s1!=0&&s2!=0)// s1==0即全都不建基站，不成立 / s2==0即全都建基站，在minn初始化的时候已经算过 { memset(bj,0,sizeof(bj));//存放基站的辐射半径 sum=INF; //基站的辐射半径和 dfs(1); minn=min(minn,Cs*s2+Cr*sum); } } void judge() { //用01的全排列，1表示在该地方建基站，0表示不建 for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++) vis[j]=1; for(int j=1; j<=i; j++)//有i个建基站的建筑 vis[j]=0; do { fun();//枚举这i个基站分别建在呢个建筑 } while(next_permutation(vis+1,vis+n+1)); } } 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",&a[i],&b[i]); minn=Cs*n;//每座建筑都建立基站 judge(); printf("%.2f\n",minn); } return 0; }