「NOI2007」 社交网络

题目连接

题目分析

不知道为什么，很自然地就想到了Floyed。然后冷静分析一波，发现就是个简单的DP。

令$Count[i][j][k]$表示从$i$到$j$经过$k$的最短路条数，同时令$C[i][j]$表示从$i$到$j$的最短路条数。Floyed的过程实际上就是DP的过程。我们走从$i$到$k$再到$j$的时候，要同时维护最短路数。而维护的时候需要枚举每一个点，同时注意点$k$的单独计算即可。

参考程序

#include <bits/stdc++.h>
#define LL long long
#define LD long double
using namespace std;

const LL Maxn = 110;
LL N, M, Map[ Maxn ][ Maxn ], C[ Maxn ][ Maxn ], Count[ Maxn ][ Maxn ][ Maxn ];

int main() {
    memset( Map, 255, sizeof( Map ) );
    scanf( "%lld%lld", &N, &M );
    for( LL i = 1; i <= M; ++i ) {
        LL a, b, c;
        scanf( "%lld%lld%lld", &a, &b, &c );
        Map[ a ][ b ] = Map[ b ][ a ] = c;
        C[ a ][ b ] = Count[ a ][ b ][ a ] = Count[ a ][ b ][ b ] = 1;
        C[ b ][ a ] = Count[ b ][ a ][ a ] = Count[ b ][ a ][ b ] = 1;
    }
    for( LL i = 1; i <= N; ++i ) {
        Map[ i ][ i ] = 0;
        C[ i ][ i ] = Count[ i ][ i ][ i ] = 1;
    }
    for( LL k = 1; k <= N; ++k ) 
        for( LL i = 1; i <= N; ++i )
            for( LL j = 1; j <= N; ++j ) {
                if( i == j || i == k || j == k ) continue;
                if( Map[ i ][ k ] == -1 || Map[ k ][ j ] == -1 ) continue;
                if( Map[ i ][ j ] == Map[ i ][ k ] + Map[ k ][ j ] ) {
                    for( LL p = 1; p <= N; ++p ) 
                        if( p != k )
                            Count[ i ][ j ][ p ] += Count[ i ][ k ][ p ] * C[ k ][ j ] + C[ i ][ k ] * Count[ k ][ j ][ p ];
                        else 
                            Count[ i ][ j ][ p ] += C[ i ][ k ] * C[ k ][ j ];
                    C[ i ][ j ] += C[ i ][ k ] * C[ k ][ j ];
                    continue;
                }
                if( Map[ i ][ j ] == -1 || Map[ i ][ j ] > Map[ i ][ k ] + Map[ k ][ j ] ) {
                    Map[ i ][ j ] = Map[ i ][ k ] + Map[ k ][ j ];
                    for( LL p = 1; p <= N; ++p )
                        if( p != k )
                            Count[ i ][ j ][ p ] = Count[ i ][ k ][ p ] * C[ k ][ j ] + C[ i ][ k ] * Count[ k ][ j ][ p ];
                        else 
                            Count[ i ][ j ][ p ] = C[ i ][ k ] * C[ k ][ j ];
                    C[ i ][ j ] = C[ i ][ k ] * C[ k ][ j ];
                }
            }
//    for( LL i = 1; i <= N; ++i ) {
//        for( LL j = 1; j <= N; ++j ) { 
//            printf( "%lld", Map[ i ][ j ] );
//            printf( "(%lld, ", C[ i ][ j ] );
//            for( LL k = 1; k < N; ++k ) printf( "%lld ", Count[ i ][ j ][ k ] ); 
//            printf( "%lld) ", Count[ i ][ j ][ N ] );
//        }
//        printf( "\n" );
//    }
    for( LL i = 1; i <= N; ++i ) {
        LD Ans = 0;
        for( LL j = 1; j <= N; ++j )
            for( LL k = 1; k <= N; ++k ) {
                if( i == j || i == k || j == k ) continue;
                Ans += 1.0 * Count[ j ][ k ][ i ] / C[ j ][ k ];
            }
        printf( "%.3Lf\n", Ans );
    }
    return 0;
}