1491: [NOI2007]社交网络（Floyd）

题目：http://www.lydsy.com/JudgeOnline/problem.php?id=1491

貌似好久木有发过题解了？之前几天一直都在刷USACO月赛的水题，实在没什么可以写的，都是些模拟，水DP神马的，以后再来整理一下好了，废话少说了，对于这道题，刚开始想用n次SPFA搞，结果死活想不出来怎么处理路径数，然后去ORZ了一下BYVOID大神的BLOG之后才发现用FLOYD其实就够了，FLOYD的过程中顺便把最短路的数目处理出来，然后就乘法原理搞一下啦~

代码：

a8773912b31bb0512957b146347adab44aede069.jpg.png

#include <cstdio>
#include <algorithm>
#include <cstring>
 
using namespace std ;
 
#define MAXN 110
#define rep( i , x ) for ( int i = 0 ; i ++ < x ; )
 
const double inf = 1e20 ;
 
double dist[ MAXN ][ MAXN ] , num[ MAXN ][ MAXN ] ;
int n , m ; 
 
int main(  ) {
    scanf( "%d%d" , &n , &m ) ; rep( i , n ) rep( j , n ) dist[ i ][ j ] = inf , num[ i ][ j ] = 0 ;
    while ( m -- ) {
        int s , t ; double d ; scanf( "%d%d%lf" , &s , &t , &d ) ;
        dist[ s ][ t ] = dist[ t ][ s ] = d , num[ s ][ t ] = num[ t ][ s ] = 1 ;
    }
    rep( k , n ) rep( i , n ) rep( j , n ) if ( dist[ i ][ k ] < inf && dist[ k ][ j ] < inf ) {
        if ( dist[ i ][ k ] + dist[ k ][ j ] < dist[ i ][ j ] ) {
            dist[ i ][ j ] = dist[ i ][ k ] + dist[ k ][ j ] ;
            num[ i ][ j ] = num[ i ][ k ] * num[ k ][ j ] ;
        } else if ( dist[ i ][ k ] + dist[ k ][ j ] == dist[ i ][ j ] ) {
            num[ i ][ j ] += num[ i ][ k ] * num[ k ][ j ] ;
        }
    }
    rep( i , n ) {
        double I = 0 ;
        rep( s , n ) rep( t , n ) if ( s != t && s != i && t != i && dist[ s ][ t ] == dist[ s ][ i ] + dist[ i ][ t ] ) {
            I += ( num[ s ][ i ] * num[ i ][ t ] ) / num[ s ][ t ] ;
        }
        printf( "%.3f\n" , I ) ;
    }
    return 0 ;
}