Submission #2298446

---

Source Code Expand

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

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

struct UnionFindTree{
    vector<int>par,sz;
    UnionFindTree(int n){
        par.resize(n);
        sz.resize(n);
        for(int i=0;i<n;i++){
            par[i]=i;
            sz[i]=1;
        }
    }
    int find(int x){
        return x==par[x]?x:par[x]=find(par[x]);
    }
    void unite(int x,int y){
        x=find(x);y=find(y);
        if(x==y)return;
        if(sz[x]<sz[y])swap(x,y);
        sz[x]+=sz[y];
        par[y]=x;
    }
    bool areSame(int x,int y){
        return find(x)==find(y);
    }
    int size(int x){
        return sz[find(x)];
    }
};

int N;
int X[15],Y[15],A[15];

double ei[1<<15];
double dp[1<<15];


signed main(){
    cin>>N;
    rep(i,N)cin>>X[i]>>Y[i]>>A[i];

    for(int i=1;i<1<<N;i++){
        vector<tuple<int,int,int>>es;
        rep(j,N){
            if(~i>>j&1)continue;
            for(int k=j+1;k<N;k++){
                if(~i>>k&1)continue;
                int d=(X[j]-X[k])*(X[j]-X[k])+(Y[j]-Y[k])*(Y[j]-Y[k]);
                es.pb(make_tuple(d,j,k));
            }
        }
        sort(all(es));
        UnionFindTree uf(N);
        double sum=0;
        rep(j,N)if(i>>j&1)sum+=A[j];
        for(auto &w:es){
            int d,u,v;
            tie(d,u,v)=w;
            if(uf.areSame(u,v))continue;
            uf.unite(u,v);
            sum-=sqrt(d);
        }
        ei[i]=sum/__builtin_popcount(i);
    }

    dp[0]=1e20;
    rep(i,1<<N){
        int sup=(1<<N)-1-i;
        for(int j=sup;j;j=(j-1)&sup){
            chmax(dp[i|j],min(dp[i],ei[j]));
        }
    }


    printf("%.20f\n",dp[(1<<N)-1]);
    return 0;
}

Submission Info

Judge Result