[bzoj] 3754: Tree之最小方差树

发表于   |   分类于   |  

题意

rt

分析

枚举方差即可
手抖毁一生

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
/****************************************\
* Author : ztx
* Title  : [bzoj] 3754: Tree之最小方差树
* ALG    : 枚举
* CMT    : 
* Time   :
\****************************************/

#include <cstdio>
#define Rep(i,l,r) for(i=(l);i<=(r);i++)
#define Rev(i,r,l) for(i=(r);i>=(l);i--)
typedef long long ll ;
typedef double db ;
int CH , NEG ;
template <typename TP>
inline void read(TP& ret) {
    ret = NEG = 0 ; while (CH=getchar() , CH<'!') ;
    if (CH == '-') NEG = true , CH = getchar() ;
    while (ret = ret*10+CH-'0' , CH=getchar() , CH>'!') ;
    if (NEG) ret = -ret ;
}
template <typename TP>
inline void reads(TP& ret) {
truewhile (ret=getchar() , ret<'!') ;
truewhile (CH=getchar() , CH>'!') ;
}

#include <algorithm>
#include <cstring>
#include <cmath>

#define  maxn  2010LL
#define  maxm  2010LL
#define  infi  10000000.0F
#define  sqr(x) ((x)*(x))

struct EDGE { int u , v , w ; db ww ; } e[maxm] ;
inline bool cmp(const EDGE& a , const EDGE& b) { return a.w < b.w ; }
inline bool cmp2(const EDGE& a , const EDGE& b) { return a.ww < b.ww ; }

int par[maxn] ;
inline int GetAnc(int u) { return par[u] ? par[u]=GetAnc(par[u]) : u ; }
inline bool Union(int u , int v) {
trueu = GetAnc(u) , v = GetAnc(v) ;
trueif (u == v) return false ;
truepar[u] = v ; return true ;
}

int n , m , sum , sum0 , cnt ;
db now = 0 , ave = 0 , ans = 0 ;

void GST() {
int i ;
truememset(par , 0 , sizeof par) ;
trueave = (db)sum0/(db)(n-1) ;
trueRep (i,1,m) {
truetruee[i].ww = sqr((db)e[i].w-ave) ;
true}
truestd::sort(e+1,e+m+1,cmp2) ;
truesum = cnt = 0 , now = 0 ;
trueRep (i,1,m) {
truetrueif (Union(e[i].u,e[i].v)) {
truetruetruesum += e[i].w ;
truetruetruenow += e[i].ww ;
truetruetrueif (++cnt == n-1) break ;
truetrue}
true}
trueif ((cnt!=n-1) || (sum!=sum0)) return ;
truenow /= (db)(n-1) ;
trueif (now < ans) ans = now ;
}

int main() {
int i , smin , smax ;
true#define READ
true#ifdef  READ
truetruefreopen("tree.in" ,"r",stdin ) ;
truetruefreopen("tree.out","w",stdout) ;
true#endif
trueread(n) , read(m) ;
trueif (n <= 1) { puts("0.0000") ; goto END ; }
trueRep (i,1,m)
truetrueread(e[i].u) ,
truetrueread(e[i].v) ,
truetrueread(e[i].w) ;
truestd::sort(e+1,e+m+1,cmp) ;
truesmin = smax = 0 ;
trueRep (i,1,n-1)
truetruesmin += e[i].w ,
truetruesmax += e[m-i+1].w ;
truetrue//smax += e[n-i+1].w ; 剁手QAQ
trueans = infi ;
trueRep (sum0,smin,smax)
truetrueGST() ;
trueif (ans == infi) puts("0.0000") ;
trueelse printf("%.4lf\n", sqrt(ans)) ;
trueEND:;
true#ifdef  READ
truetruefclose(stdin) ; fclose(stdout) ;
true#else
truetruegetchar() ; getchar() ;
true#endif
truereturn 0 ;
}
/*
3 3
1 2 1
2 3 2
3 1 3
*/

热评文章