Submission #4184954

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;

#define MAX 1<<15

int n;

double cost[MAX];

vector<pair<double,double> > v;


double dist(int a,int b){
	return sqrt((v[a].first-v[b].first)*(v[a].first-v[b].first)+(v[a].second-v[b].second)*(v[a].second-v[b].second));
}
struct st{
	int a;
	int b;
	double c;
};
bool operator<(const st a,const st b){
	return a.c<b.c;
}
vector<st> ed;
int belong[MAX];
inline int root(int b){
	if(belong[b]==-1){
		return b;
	}
	return belong[b]=root(belong[b]);
}
inline void merge(int a,int b){
	a=root(a);
	b=root(b);
	if(a==b)return;
	belong[a]=b;
}
double dp[1<<15];
vector<double> C;

int main(){
	cin>>n;
	for(int i=0;i<n;i++){
		int a,b,c;
		cin>>a>>b>>c;
		v.push_back({a,b});
		C.push_back(c);
	}
	for(int i=1;i<(1<<n);i++){
		double node=0;
		double num=0;
		memset(belong,-1,sizeof(belong));
		ed.clear();
		for(int j=0;j<n;j++){
			if(((i>>j)&1)==0)continue;
			num+=1;
			node+=C[j];
			for(int k=j+1;k<n;k++){
				if(((i>>k)&1)==0)continue;
				ed.push_back({j,k,dist(j,k)});
			}
		}
		sort(ed.begin(),ed.end());
		for(auto &it:ed){
			if(root(it.a)!=root(it.b)){
				merge(it.a,it.b);
				cost[i]+=it.c;
			}
		}
		node-=cost[i];
		node/=num;
		//cout<<node<<endl;
		node=max(node,0.0);
		cost[i]=node;
	}
	dp[0]=LLONG_MAX;
	for(int i=0;i<(1<<n);i++){
		for(int j=((i+1)|i);j<(1<<n);j++,j|=i){
			int ex=(j^i);
			dp[j]=max(dp[j],min(dp[i],cost[ex]));
		}
	}
	printf("%.16f\n",dp[(1<<n)-1]);
	return 0;
}

Submission Info

Judge Result