Submission #1004141

---

Source Code Expand

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){return o<<"("<<p.fs<<","<<p.sc<<")";}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){o<<"sz = "<<vc.size()<<endl<<"[";for(const T& v:vc) o<<v<<",";o<<"]";return o;}
struct unionfind{
	int par[16];
	void init(int N){rep(i,N) par[i]=i;}
	int find(int x){
		if(par[x]==x) return x;
		return par[x]=find(par[x]);
	}
	bool same(int x,int y){
		return find(x)==find(y);
	}
	void unite(int x,int y){
		x=find(x),y=find(y);
		if(x==y) return;
		par[y]=x;
	}
}UF;

typedef pair<int,int> P;
typedef pair<double,P> edge;
int N;
double x[16],y[16],a[16];
double c[1<<16];
double dp[1<<16];
vector<edge> es;
double inf=1e50;
bool B(int x,int i){return (x>>i)&1;}
int main(){
	int N;
	cin>>N;
	rep(i,N) cin>>x[i]>>y[i]>>a[i];
	rep(i,N) rep(j,i){
		double dis=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
		es.pb(edge(dis,P(j,i)));
	}
	sort(all(es));
	rep(b,1<<N){
		if(b==0) continue;
		UF.init(N);
		double sum=0;
		rep(i,N) if(B(b,i)) sum+=a[i];
		for(edge e:es){
			double d=e.fs;
			int x=e.sc.fs,y=e.sc.sc;
			if(B(b,x)&&B(b,y)&&!UF.same(x,y)){
				sum-=d;
				UF.unite(x,y);
			}
		}
		c[b]=max(0.0,sum/__builtin_popcount(b));
	}
	dp[0]=inf;
	rep(b,1<<N){
		int left=(1<<N)-1-b;
		int x=left;
		do{
			chmax(dp[b|x],min(dp[b],c[x]));
			x=(x-1)&left;
		}while(x!=0);
	}
	printf("%.12f\n",dp[(1<<N)-1]);
}

Submission Info

Judge Result