Submission #4127488

---

Source Code Expand

#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>
#include <cmath>
using namespace std;

class UnionFind {
public:
	vector<int>par;

	void init(int size_) {
		par.resize(size_, -1);
	}
	int root(int pos) {
		if (par[pos] == -1) return pos;
		par[pos] = root(par[pos]);
		return par[pos];
	}
	void unite(int u, int v) {
		u = root(u); v = root(v);
		if (u != v) par[u] = v;
	}
	bool same(int u, int v) {
		if (root(u) == root(v)) return true;
		return false;
	}
};

long long N, x[19], y[19], a[19]; long double r[1 << 17], dp[1 << 17];

int main() {
	cin >> N;
	for (int i = 0; i < N; i++) cin >> x[i] >> y[i] >> a[i];

	for (int i = 0; i < (1 << N); i++) {
		int bit[15], cnt = 0; for (int j = 0; j < N; j++) { bit[j] = (i / (1 << j)) % 2; cnt += bit[j]; }

		vector<tuple<long double, int, int>>vec;
		for (int j = 0; j < N; j++) {
			for (int k = j + 1; k < N; k++) {
				if (bit[j] == 1 && bit[k] == 1) {
					long double leng = sqrtl(1.0L * (x[j] - x[k]) * (x[j] - x[k]) + 1.0L * (y[j] - y[k]) * (y[j] - y[k]));
					vec.push_back(make_tuple(leng, j, k));
				}
			}
		}
		sort(vec.begin(), vec.end());

		UnionFind UF; UF.init(N); long double sum = 0;
		for (int j = 0; j < vec.size(); j++) {
			int to1 = get<1>(vec[j]), to2 = get<2>(vec[j]);
			if (UF.same(to1, to2) == false) {
				sum += get<0>(vec[j]); UF.unite(to1, to2);
			}
		}

		long double A = 0; for (int j = 0; j < N; j++) A += 1.0L * bit[j] * a[j];
		r[i] = 1.0L * (A - sum) / cnt;
	}

	dp[0] = 1e9;
	for (int i = 0; i < (1 << N); i++) {
		vector<int>vec; for (int j = 0; j < N; j++) { if ((i / (1 << j)) % 2 == 0) vec.push_back(j); }
		
		for (int j = 0; j < (1 << vec.size()); j++) {
			int S = 0; for (int k = 0; k < vec.size(); k++) { if ((j&(1 << k)) != 0) S += (1 << vec[k]); }
			dp[i + S] = max(dp[i + S], min(dp[i], r[S]));
		}
	}
	printf("%.12Lf\n", dp[(1 << N) - 1]);
	return 0;
}

Submission Info

Judge Result