1 /************************************************************** 2     Problem: 3754 3     User: rausen 4     Language: C++ 5     Result: Accepted 6     Time:9024 ms 7     Memory:892 kb 8 ****************************************************************/ 9  10 #include <cstdio>11 #include <cmath>12 #include <algorithm>13  14 using namespace std;15 typedef double lf;16 const int N = 105;17 const int M = 2005;18 const int Maxlen = 30005;19  20 struct edges {21     int x, y, v;22     lf w;23      24     inline bool operator < (const edges &b) const {25         return w < b.w;26     }27 } e[M];28 inline bool cmp_min(edges a, edges b) {29     return a.v < b.v;30 }31 inline bool cmp_max(edges a, edges b) {32     return a.v > b.v;33 }34  35  36 int n,m, Min, Max, fa[N];37 lf ans = (lf) 1e15;38  39 char buf[Maxlen], *c = buf;40 int Len;41  42 inline int read() {43     int x = 0;44     while (*c < ‘0‘ || ‘9‘ < *c) ++c;45     while (‘0‘ <= *c && *c <= ‘9‘)46         x = x * 10 + *c - ‘0‘, ++c;47     return x;48 }49  50 lf Sqr(lf x) {51     return x * x;52 }53  54 int find(int x) {55     return x == fa[x] ? x : fa[x] = find(fa[x]);56 }57  58 void work(int sum) {59     lf A = (lf) sum / (n - 1), res = 0;60     int cost = 0, tot = 0, fa1, fa2, i;61     for (i = 1; i <= n; ++i)62         fa[i] = i;63     for (i = 1; i <= m; ++i)64         e[i].w = Sqr((lf) e[i].v - A);65     sort(e + 1, e + m + 1);66     for (i = 1; i <= m; ++i)67         if ((fa1 = find(e[i].x)) != (fa2 = find(e[i].y))) {68             fa[fa1] = fa2;69             cost += e[i].v;70             res += e[i].w;71             if (++tot == n - 1) break;72         }73     if (cost == sum)74         ans = min(ans, res);75 }76  77 int main() {78     int i;79     Len = fread(c, 1, Maxlen, stdin);80     buf[Len] = ‘\0‘;81     n = read(), m = read();82     for (i = 1; i <= m; ++i)83         e[i].x = read(), e[i].y = read(), e[i].v = read();84     sort(e + 1, e + m + 1, cmp_min);85     for (i = 1; i < n; ++i)86         Min += e[i].v;87     sort(e + 1, e + m + 1, cmp_max);88     for (i = 1; i < n; ++i)89         Max += e[i].v;90     for (i = Min; i <= Max; ++i)91         work(i);92     printf("%.4lf\n", sqrt((lf) ans / (n - 1)));93 }