记录编号	308502	评测结果	AAAAAAAAAA
题目名称	[HZOI 2016]生日快乐！小埋!	最终得分	100
用户昵称	Magic_Sheep	是否通过	通过
代码语言	C++	运行时间	0.825 s
提交时间	2016-09-18 08:12:33	内存使用	27.09 MiB

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=10100;
int cnt,f[maxn],n,m;
double w[5000500],ans=999999999999.00;
bool vis[maxn];
struct node
{
    int x,y,z;
    double val;
};
node t[maxn];
inline bool cmp(const node &i,const node &j)
{
    return i.z<j.z;
}
inline bool cmp1(const node &i,const node &j)
{
    return i.val<j.val;
}
inline int find(int x)
{
    if(f[x]==x) return x;
    else return f[x]=find(f[x]);
}
inline double spt(double x){return x*x;}
inline double work(double mid)
{
    memset(vis,false,sizeof(vis));
    for(int i=1;i<=n;i++) f[i]=i;
    for(int i=1;i<=m;i++) t[i].val=spt(t[i].z-mid);
    sort(t+1,t+1+m,cmp1);int sum=n;double cur=0.00;
    for(int i=1;i<=m;i++)
    {
        if(sum==1) break;
        int fx=find(t[i].x),fy=find(t[i].y);
        if(fx!=fy)
        {
            f[fx]=fy;sum--;
            cur+=t[i].z;vis[i]=true;
            //cout<<cur<<endl;
        }
    }
    double res=0.00,ave=cur/(n-1);
    //cout<<ave<<endl;
    for(int i=1;i<=m;i++)
    {
        if(vis[i]) res+=spt(t[i].z-ave);
        //cout<<res<<endl;
    }
    return sqrt(res/(n-1));
}
int MAIN()
{
    freopen("happy_birthday.in","r",stdin);
    freopen("happy_birthday.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&t[i].x,&t[i].y,&t[i].z);
    }
    sort(t+1,t+1+m,cmp);
    for(int i=1;i<=m;i++)
    {
        for(int j=i;j<=m;j++)
        {
            w[++cnt]=(t[i].z+t[j].z)/2.0;
        }
    }
    sort(w+1,w+1+cnt),cnt=unique(w+1,w+1+cnt)-w-1;
    ans=min(ans,work(w[1]/2.0)),ans=min(ans,work(w[cnt]+1.0));
    //cout<<work(w[1]/2.0)<<" "<<work(w[cnt]+1.0)<<endl;
    for (int i=1;i<cnt;i++) ans=min(ans,work((w[i]+w[i+1])/2.0));
    printf("%.4lf\n",ans);
    return 0;
}
int main(){;}
int EZOI=MAIN();