注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

GreenCloudS

 
 
 

日志

 
 

1491: [NOI2007]社交网络(Floyd)  

2014-01-17 19:11:00|  分类: oi,bzoj,最短路,f |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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


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


代码:

1491: [NOI2007]社交网络(Floyd) - cjjlsdy - cjjlsdy的博客

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


  评论这张
 
阅读(0)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018