样例1
3
0 0 10
2 0 5
0 5 8
6.500000000000
样例2
15
335279264 849598327 822889311
446755913 526239859 548830120
181424399 715477619 342858071
625711486 448565595 480845266
647639160 467825612 449656269
160714711 336869678 545923679
61020590 573085537 816372580
626006012 389312924 135599877
547865075 511429216 605997004
561330066 539239436 921749002
650693494 63219754 786119025
849028504 632532642 655702582
285323416 611583586 211428413
990607689 590857173 393671555
560686330 679513171 501983447
434666178.237122833729
#include<bits/stdc++.h>
using namespace std;
int n,fa[20],k[20];
struct node
{
long long x,y,a;
};
node a[20];
struct mine
{
int x,y;
double v;
};
double dis[20][20],c[1000010],dp[1000010];
bool cmp(mine x,mine y)
{
return x.v<y.v;
}
int find(int x)
{
if(fa[x]!=x)
{
fa[x]=find(fa[x]);
}
return fa[x];
}
void f(int x)//最小生成树（kruskal）
{
mine use[250];
int idx=0,cnt=0;
for(int i=1;i<=n;i++)
{
if(((1<<i-1)&x)==0)
{
continue;
}
for(int j=1;j<=n;j++)
{
if(i==j||((1<<j-1)&x)==0)
{
continue;
}
use[++idx]={i,j,dis[i][j]};//插入边
}
}
sort(use+1,use+idx+1,cmp);//排序
for(int i=1;i<=n;i++)
{
fa[i]=i;
if(((1<<i-1)&x)!=0)
{
c[x]+=a[i].a;
cnt++;
}
}
int fx,fy;
for(int i=1;i<=idx;i++)//贪心求最小生成树
{
fx=find(use[i].x);
fy=find(use[i].y);
if(fx==fy)
{
continue;
}
fa[fx]=fy;
c[x]-=use[i].v;
}
c[x]=c[x]/((double)cnt);
return;
}
void dfs(int u,int x,int y,int cnt)//搜索dp[u]的答案
{
if(x==y+1)
{
dp[u]=max(dp[u],min(dp[cnt],dp[u^cnt]));
return;
}
dfs(u,x+1,y,cnt+(1<<k[x]-1));
dfs(u,x+1,y,cnt);
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i].x>>a[i].y>>a[i].a;
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(i==j)
{
continue;
}
dis[i][j]=sqrt((a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y));
}
}
c[0]=2e9;
for(int i=1;i<(1<<n);i++)
{
f(i);//更新每个点集强制形成一棵树的答案
}
for(int i=0;i<(1<<n);i++)
{
dp[i]=c[i];
int idx=0;
for(int j=0;j<=n;j++)
{
if(i&(1<<j-1))
{
k[++idx]=j;
}
}
dfs(i,1,idx,0);
//上面的代码相当于dp[i]=max(c[i],max(dp[j],dp[i^j]));
}
printf("%.12llf",dp[(1<<n)-1]);
return 0;
}
