题解

5 条题解

  • 1
    @ 2023-07-24 15:45:17
    #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;
    }
    
  • 0
    @ 2015-11-22 17:19:15

    输出要用%f orz

  • 0
    @ 2014-06-10 15:48:49

    #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 ;
    }

  • 0
    @ 2013-08-29 20:00:11

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

    • @ 2015-06-27 21:31:46

      我还以为是标算。。。。50分算法就不要贴出来了

  • 1

信息

ID
1807
难度
7
分类
(无)
标签
递交数
202
已通过
42
通过率
21%
被复制
2
上传者