UVALive - 5713

https://vjudge.net/problem/UVALive-5713

首先明确题意

①希望使n个城市联通且道路最短

②可以修一条魔法道路不花钱 

③设A为魔法道路连接的两座城市的人口之和，B为总花费，希望使得A/B最大

就是非严格次小生成树

又被double锤爆了呜呜呜

#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
#include<cstring>
#include<cmath>

#define ri register int
#define u int
#define NN 1005
#define MM 1005*1005

namespace fast {
    inline u in() {
        u x(0);
        char s=getchar();
        while(s<'0'||s>'9') {
            s=getchar();
        }
        while(s>='0'&&s<='9') {
            x=(x<<1)+(x<<3)+s-'0';
            s=getchar();
        }
        return x;
    }
}

using fast::in;
using std::queue;
using std::pair;

namespace cas {
    u fa[NN];
    inline u getfa(u x) {
        u r(x),k;
        while(fa[r]^r) {
            r=fa[r];
        }
        while(x^r) {
            k=x,x=fa[x],fa[k]=r;
        }
        return r;
    }
    inline void pri(const u &n) {
        for(ri i=1; i<=n; ++i)fa[i]=i;
    }
}

using namespace cas;

namespace all {
    u N,M,T,cnt,h[NN];
    struct node {
        u to,next;
        double va;
    } a[MM];
    inline void add(const u &x,const u &y,const double &z) {
        a[++cnt].next=h[x],a[cnt].to=y,a[cnt].va=z,h[x]=cnt;
    }

    struct node1 {
        u x,y,z;
    } b[NN];
    u num,n;
    struct node2 {
        u x,y;
        double z;
    } c[MM];
    double calc(const double &x,const double &y,const double &xx,const double &yy) {
        return std::sqrt((x-xx)*(x-xx)+(y-yy)*(y-yy));
    }
    bool cmp(const node2 &x,const node2 &y) {
        return x.z<y.z;
    }
    double m[NN][NN],g[NN][NN];

    double dfs(const u &x,const u &y,const u &prt,double mi) {
        if(g[x][y]) return g[x][y];
        if(x^y) {
            double _re;
            for(ri i(h[x]); i; i=a[i].next) {
                u _y(a[i].to);
                if(_y==prt) continue;
                _re=std::max(mi,a[i].va);
                double _r=dfs(_y,y,x,_re);
                if(_r>0) {
                    return _r;
                }
            }
            return 0;
        } else {
            return mi;
        }
    }

    inline void solve() {
        T=in();
        while(T--) {
            n=num=cnt=0;
            std::memset(h,0,sizeof(h));
            std::memset(m,0,sizeof(m));
            std::memset(g,0,sizeof(g));
            N=in();
            for(ri i(1); i<=N; ++i) {
                u _x(in()),_y(in()),_z(in());
                b[i].x=_x,b[i].y=_y,b[i].z=_z;//点 坐标，人数
            }
            for(ri i(1); i<=N; ++i) {
                for(ri j(1); j<=N; ++j) {
                    if(i^j) {
                        c[++num].x=i,c[num].y=j;
                        c[num].z=calc((double)b[i].x,(double)b[i].y,(double)b[j].x,(double)b[j].y);//边 两点，距离
                    }
                }
            }
            std::sort(c+1,c+num+1,cmp);
            u _cnt(0);
            double ans(0.0);
            pri(N);
            while(n<N-1) {
                u fx(getfa(c[++_cnt].x)),fy(getfa(c[_cnt].y));
                if(fx^fy) {
                    fa[fx]=fy,++n,ans+=c[_cnt].z;
                    add(c[_cnt].x,c[_cnt].y,c[_cnt].z);
                    add(c[_cnt].y,c[_cnt].x,c[_cnt].z);
                    m[c[_cnt].x][c[_cnt].y]=m[c[_cnt].y][c[_cnt].x]=c[_cnt].z;
                }
            }
            double as(0);
            for(ri i(1); i<=N; ++i) {
                for(ri j(i+1); j<=N; ++j) {
                    double _a(b[i].z+b[j].z),_b(ans);
                    if(m[i][j]) {
                        _b-=m[i][j];
                    } else {
                        _b-=(g[i][j]=g[j][i]=dfs(i,j,0,0));
                    }
                    as=std::max(as,_a/_b);
                    /*if(as>6.324) {
                        u _p(0);
                    }*/
                }
            }
            printf("%.2lf\n",as);
        }
    }
}

int main() {
    //freopen("x.txt","r",stdin);
    all::solve();
}