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

GreenCloudS

 
 
 

日志

 
 

BZOJ-2750: [HAOI2012]Road(SPFA+拓扑DP)  

2014-06-08 21:11:00|  分类: oi,bzoj,dp,最短 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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


太久没刷水题的话对身体不好啊~~~~~~于是乎我又来刷水题啦~

嘛嘛,这题思路挺清晰的,先枚举源点,然后最短路n次,每次都正向和反向在最短路树上拓扑DP统计路径条数,然后某边如果在最短路上就乘起来,最后累加就好啦~


代码(没用DJ用了SPFA没想到还挺快的。。。):

  • #include <cstdio>

  • #include <algorithm>

  • #include <cstring>

  • #include <deque>

  •  

  • using namespace std ;

  •  

  • #define travel( x ) for ( edge *p = head[ x ] ; p ; p = p -> next )

  • #define rep( i , x ) for ( int i = 0 ; i ++ < x ; )

  • #define REP( i , l , r ) for ( int i = l ; i <= r ; ++ i )

  •  

  • #define pf push_front

  • #define pb push_back

  •  

  • typedef long long ll ;

  •  

  • const int maxn = 1510 , maxm = 5010 , inf = 0x7ffffff ;

  • const ll mod = 1000000007 ;

  •  

  • inline ll add( ll val , ll del ) {

  •     return ( val + del ) % mod ;

  • }

  •  

  • inline ll mul( ll x , ll y ) {

  •     return ( x * y ) % mod ;

  • }

  •  

  • struct graph {

  •      

  •     struct edge {

  •         int t , d ;

  •         edge *next ;

  •     } E[ maxm ] ;

  •      

  •     edge *head[ maxn ] , *pt ;

  •      

  •     inline void addedge( int s , int t , int d ) {

  •         pt -> t = t , pt -> d = d , pt -> next = head[ s ] ;

  •         head[ s ] = pt ++ ;

  •     }

  •      

  •     deque < int > q ;

  •     bool used[ maxn ] ;

  •     int dist[ maxn ] , V ;

  •      

  •     inline void Init( int _V ) {

  •         V = _V , pt = E ;

  •         rep( i , V ) head[ i ] = NULL ;

  •     }

  •      

  •     inline void spfa( int S ) {

  •         rep( i , V ) {

  •             used[ i ] = false , dist[ i ] = inf ;

  •         }

  •         q.clear(  ) ;

  •         dist[ S ] = 0 , used[ S ] = true , q.pb( S ) ;

  •         int now , cost ;

  •         while ( ! q.empty(  ) ) {

  •             now = q.front(  ) ; q.pop_front(  ) , used[ now ] = false ;

  •             travel( now ) if ( ( cost = dist[ now ] + p -> d ) < dist[ p -> t ] ) {

  •                 dist[ p -> t ] = cost ;

  •                 if ( ! used[ p -> t ] ) {

  •                     used[ p -> t ] = true ;

  •                     if ( q.empty(  ) ) q.pb( p -> t ) ; else if ( cost < dist[ q.front(  ) ] ) q.pf( p -> t ) ; else q.pb( p -> t ) ;

  •                 }

  •             }

  •         }

  •     }

  •      

  •     ll f[ maxn ] ;

  •     int d[ maxn ] ;

  •      

  •     inline void dp(  ) {

  •         rep( i , V ) d[ i ] = 0 ;

  •         q.clear(  ) ;

  •         rep( i , V ) travel( i ) ++ d[ p -> t ] ;

  •         rep( i , V ) if ( ! d[ i ] ) q.pb( i ) ;

  •         int now ;

  •         while ( ! q.empty(  ) ) {

  •             now = q.front(  ) ; q.pop_front(  ) ;

  •             travel( now ) {

  •                 f[ p -> t ] = add( f[ p -> t ] , f[ now ] ) ;

  •                 if ( ! ( -- d[ p -> t ] ) ) q.pb( p -> t ) ;

  •             }

  •         }

  •     }

  •       

  • } g , T , IT ;

  •  

  • int n , m , e[ maxm ][ 3 ] ;

  • ll ans[ maxm ] ;

  •  

  • int main(  ) {

  •     scanf( "%d%d" , &n , &m ) ;

  •     g.Init( n ) ;

  •     int s , t , d ;

  •     rep( i , m ) {

  •         scanf( "%d%d%d" , &e[ i ][ 0 ] , &e[ i ][ 1 ] , &e[ i ][ 2 ] ) ;

  •         g.addedge( e[ i ][ 0 ] , e[ i ][ 1 ] , e[ i ][ 2 ] ) ;

  •     }

  •     rep( i , n ) {

  •         g.spfa( i ) , T.Init( n ) , IT.Init( n ) ;

  •         rep( j , m ) {

  •             s = e[ j ][ 0 ] , t = e[ j ][ 1 ] , d = e[ j ][ 2 ] ;

  •             if ( g.dist[ t ] == g.dist[ s ] + d ) {

  •                 T.addedge( s , t , 0 ) , IT.addedge( t , s , 0 ) ;

  •             }

  •         }

  •         rep( j , n ) {

  •             T.f[ j ] = 0 , IT.f[ j ] = 1 ;

  •         }

  •         T.f[ i ] = 1 ;

  •         T.dp(  ) , IT.dp(  ) ;

  •         rep( j , m ) {

  •             s = e[ j ][ 0 ] , t = e[ j ][ 1 ] , d = e[ j ][ 2 ] ;

  •             if ( g.dist[ t ] == g.dist[ s ] + d ) {

  •                 ans[ j ] = add( ans[ j ] , mul( T.f[ s ] , IT.f[ t ] ) ) ;

  •             }

  •         }

  •     }

  •     rep( i , m ) printf( "%lld\n" , ans[ i ] ) ;

  •     return 0 ;

  • }



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

历史上的今天

评论

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

页脚

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