Submission #1801831

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;
const int MAXN = 105;

struct edg{
	int s, e;
	double x;
	bool operator<(const edg &e)const{
		return x < e.x;
	}
};

struct disj{
	int pa[20];
	void init(int n){
		iota(pa, pa + n, 0);
	}
	int find(int x){
		return pa[x] = (pa[x] == x ? x : find(pa[x]));
	}
	bool uni(int p, int q){
		p = find(p);
		q = find(q);
		if(p == q) return 0;
		pa[q] = p; return 1;
	}
}disj;

double getmst(vector<edg> &v){
	sort(v.begin(), v.end());
	disj.init(16);
	double ans = 0;
	for(auto &i : v) if(disj.uni(i.s, i.e)) ans += i.x;
	return ans;
}

int n, x[15], y[15], z[15];
double ans[50000];

int main(){
	cin >> n;
	for(int i=0; i<n; i++) cin >> x[i] >> y[i] >> z[i];
	for(int i=1; i<(1<<n); i++){
		vector<edg> v;
		double sum = 0;
		int cnt = 0;
		for(int j=0; j<n; j++){
			if((i >> j) & 1) sum += z[j], cnt++;
		}
		for(int j=0; j<n; j++){
			for(int k=0; k<j; k++){
				if((i >> j) % 2 == 1 && (i >> k) % 2 == 1){
					double dx = hypot(x[j] - x[k], y[j] - y[k]);
					v.push_back({j, k, dx});
				}
			}
		}
		ans[i] = (sum - getmst(v)) / cnt;
	}
	for(int i=1; i<(1<<n); i++){
		for(int j=i; j>0; j = (j - 1) & i){
			int x = j, y = i ^ j;
			if(x && y) ans[i] = max(ans[i], min(ans[x], ans[y]));
		}
	}
	printf("%.10f\n", ans[(1<<n) - 1]);
}

Submission Info

Judge Result