#include<cstdio>
#include<cstring>
#include<algorithm>
 
using namespace std;
 
const int maxn = 100009;
 
int N, M, C, Root, deg[maxn], L[maxn], R[maxn], Lw[maxn], Rw[maxn];
bool vis[maxn];
double Eu[maxn], Ed[maxn];
 
struct edge {
    int t, w;
    edge* n;
} E[maxn << 1], *pt = E, *H[maxn];
 
inline void AddEdge(int u, int v, int w) {
    deg[pt->t = v]++, pt->w = w, pt->n = H[u], H[u] = pt++;
}
 
void DFS_D(int x) {
    vis[x] = true;
    Ed[x] = 0;
    for(edge* e = H[x]; e; e = e->n) if(!vis[e->t]) {
        DFS_D(e->t);
        Ed[x] += Ed[e->t] + e->w;
    }
    if(x == Root) {
        Ed[x] /= max(1, (deg[x] - (M < N ? 0 : 2)));
    } else if(deg[x] > 1)
        Ed[x] /= deg[x] - 1;
}
 
void DFS_U(int x) {
    vis[x] = true;
    for(edge* e = H[x]; e; e = e->n) if(!vis[e->t]) {
        int d = deg[x];
        if(x != Root) {
            d--;
        } else if(M == N)
            d -= 2;
        double t = (Ed[x] * d - Ed[e->t] - e->w);
        if(x == Root) {
            if(M < N)
                Eu[e->t] = t / max(1, d - 1);
            else
                Eu[e->t] = (t + Eu[x] * 2) / (d + 1);
        } else
            Eu[e->t] = (t + Eu[x]) / d;
        Eu[e->t] += e->w;
        DFS_U(e->t);
    }
}
 
void DFS_U(int x, int nxt[], int nxtw[], double &t, int len, double p = 0.5) {
    if(nxt[x] != Root) {
        t += (Ed[x] + len) * p * (deg[x] - 2) / (deg[x] - 1);
        DFS_U(nxt[x], nxt, nxtw, t, len + nxtw[x], p / (deg[x] - 1));
    } else
        t += (Ed[x] + len) * p;
}
 
bool DFS_C(int x, edge* r = NULL) {
    vis[x] = true;
    for(edge* e = H[x]; e; e = e->n) if(e != r) {
        L[e->t] = x;
        R[x] = e->t;
        Lw[e->t] = Rw[x] = e->w;
        if(vis[e->t]) {
            C = e->t;
            return true;
        }
        if(DFS_C(e->t, E + ((e - E) ^ 1))) return true;
    }
    return false;
}
 
void Init() {
    scanf("%d%d", &N, &M);
    int u, v, w;
    for(int i = 0; i < M; i++) {
        scanf("%d%d%d", &u, &v, &w);
        u--, v--;
        AddEdge(u, v, w);
        AddEdge(v, u, w);
    }
}
 
void Work() {
    double ans = 0;
    if(M < N) {
        memset(vis, 0, sizeof vis);
        DFS_D(Root = 0);
        memset(vis, 0, sizeof vis);
        Eu[0] = 0;
        DFS_U(Root = 0);
        ans = Ed[0];
        for(int i = 1; i < N; i++)
            ans += (Ed[i] * (deg[i] - 1) + Eu[i]) / deg[i];
    } else {
        memset(vis, 0, sizeof vis);
        DFS_C(0);
        Root = C;
        do {
            memset(vis, 0, sizeof vis);
            vis[L[Root]] = vis[R[Root]] = true;
            DFS_D(Root);
        } while((Root = L[Root]) != C);
        Root = C;
        do {
            DFS_U(L[Root], L, Lw, Eu[Root], Lw[Root]);
            DFS_U(R[Root], R, Rw, Eu[Root], Rw[Root]);
        } while((Root = L[Root]) != C);
        Root = C;
        do {
            memset(vis, 0, sizeof vis);
            vis[L[Root]] = vis[R[Root]] = true;
            DFS_U(Root);
        } while((Root = L[Root]) != C);
        memset(vis, 0, sizeof vis);
        Root = C;
        do {
            ans += (Ed[Root] * (deg[Root] - 2) + Eu[Root] * 2) / deg[Root];
            vis[Root] = true;
        } while((Root = L[Root]) != C);
        for(int i = 0; i < N; i++)
            if(!vis[i]) ans += (Ed[i] * (deg[i] - 1) + Eu[i]) / deg[i];
    }
    printf("%.5lf\n", ans / N);
}
 
int main() {
    
    Init();
    Work();
    
    return 0;
}

http://www.cnblogs.com/JSZX11556/p/5187251.html

输出要用%f orz

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std ;

#define travel( x ) for ( vector < edge > :: iterator p = E[ x ].begin( ) ; p != E[ x ].end( ) ; ++ p )
#define rep( i , x ) for ( int i = 0 ; i ++ < x ; )

#define addedge( s , t , d ) add( s , t , d ) , add( t , s , d )
#define add( s , t , d ) E[ s ].push_back( edge( t , d ) )

const int maxn = 100100 ;

struct edge {
int t , d ;
edge( int _t , int _d ) : t( _t ) , d( _d ) {
}
} ;
vector < edge > E[ maxn ] ;

double sum[ maxn ] , down[ maxn ] , up[ maxn ] , cnt[ maxn ] , d[ maxn ] ;
bool used[ maxn ] ;

void dp_down( int now , int fa ) {
cnt[ now ] = sum[ now ] = 0 ;
travel( now ) if ( p -> t != fa && ! used[ p -> t ] ) {
cnt[ now ] += 1 ;
dp_down( p -> t , now ) ;
sum[ now ] += double( p -> d ) + down[ p -> t ] ;
}
if ( cnt[ now ] ) down[ now ] = sum[ now ] / cnt[ now ] ;
}

void dp_up( int now , int fa ) {
travel( now ) if ( p -> t != fa && ! used[ p -> t ] ) {
if ( d[ now ] > 1.000001 ) up[ p -> t ] = double( p -> d ) + ( sum[ now ] - double( p -> d ) - down[ p -> t ] + up[ now ] ) / ( d[ now ] - 1 ) ; else up[ p -> t ] = double( p -> d ) + up[ now ] ;
dp_up( p -> t , now ) ;
}
}

int n , m ;

double solve0( ) {
memset( used , false , sizeof( used ) ) ;
dp_down( 1 , 0 ) ;
dp_up( 1 , 0 ) ;
double ans = 0 ;
rep( i , n ) ans += ( sum[ i ] + up[ i ] ) / d[ i ] ;
return ans / double( n ) ;
}

bool flag = false ;
int Stack[ maxn ] , Cnt = 0 , len , node[ maxn ] ;
double D[ maxn ] , dist[ maxn ] ;

void dfs( int now , int fa ) {
if ( flag ) return ;
used[ now ] = true , Stack[ Cnt ++ ] = now ;
travel( now ) if ( p -> t != fa ) if ( used[ p -> t ] ) {
if ( flag ) return ;
int i ;
for ( i = 0 ; i < Cnt && Stack[ i ] != p -> t ; ++ i ) ;
len = 0 ;
for ( ; i < Cnt ; ++ i ) {
node[ len ] = Stack[ i ] ;
dist[ len ++ ] = D[ i ] ;
}
dist[ len - 1 ] = double( p -> d ) ;
flag = true ;
return ;
} else {
D[ Cnt - 1 ] = double( p -> d ) ;
dfs( p -> t , now ) ;
}
used[ now ] = false , -- Cnt ;
}

double left[ maxn ] , right[ maxn ] ;

double solve1( ) {
memset( used , false , sizeof( used ) ) ;
dfs( 1 , 0 ) ;
memset( used , false , sizeof( used ) ) ;
for ( int i = 0 ; i < len ; ++ i ) used[ node[ i ] ] = true ;
for ( int i = 0 ; i < len ; ++ i ) dp_down( node[ i ] , 0 ) ;
memset( left , 0 , sizeof( left ) ) ;
memset( right , 0 , sizeof( right ) ) ;
for ( int i = 0 ; i < len ; ++ i ) {
left[ i ] = right[ i ] = 0 ;
for ( int p = i , j = ( i + 1 ) % len ; j != i ; ( j += 1 ) %= len , ( p += 1 ) %= len ) {
if ( d[ node[ p ] ] < 2.01 || p != i ) left[ j ] = dist[ p ] + ( ( left[ p ] + sum[ node[ p ] ] ) / ( d[ node[ p ] ] - 1 ) ) ;
else left[ j ] = dist[ p ] + ( ( left[ p ] + sum[ node[ p ] ] ) / ( d[ node[ p ] ] - 2 ) ) ;
}
for ( int p = i , j = ( i - 1 + len ) % len ; j != i ; j = ( j - 1 + len ) % len , p = ( p - 1 + len ) % len ) {
if ( d[ node[ p ] ] < 2.01 || p != i ) right[ j ] = dist[ j ] + ( right[ p ] + sum[ node[ p ] ] ) / ( d[ node[ p ] ] - 1 ) ;
else right[ j ] = dist[ j ] + ( right[ p ] + sum[ node[ p ] ] ) / ( d[ node[ p ] ] - 2 ) ;
}
up[ node[ ( i - 1 + len ) % len ] ] += left[ ( i - 1 + len ) % len ] ;
up[ node[ ( i + 1 ) % len ] ] += right[ ( i + 1 ) % len ] ;
}
for ( int i = 0 ; i < len ; ++ i ) dp_up( node[ i ] , 0 ) ;
double ans = 0 ;
for ( int i = 0 ; i ++ < n ; ) ans += ( up[ i ] + sum[ i ] ) / d[ i ] ;
return ans / double( n ) ;
}

int main( ) {
scanf( "%d%d" , &n , &m ) ;
rep( i , m ) {
int s , t , w ; scanf( "%d%d%d" , &s , &t , &w ) ;
d[ s ] += 1, d[ t ] += 1 , addedge( s , t , w ) ;
}
if ( m == n - 1 ) printf( "%.5f\n" , solve0( ) ) ; else printf( "%.5f\n" , solve1( ) ) ;
return 0 ;
}

....................................................................................................................................................................................................................................................................................................................................................................................