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

GreenCloudS

 
 
 

日志

 
 

BZOJ-2707: [SDOI2012]走迷宫(Tarjan求SCC+高斯消元)  

2014-06-07 16:09:00|  分类: oi,bzoj,SCC,tarj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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


首先缩一下SCC,然后对于不在同一块SCC里的按拓扑序递推,同一块SCC的高斯消元求解,然后判断INF的条件是存在S可以到达却到达不了T的节点,细节蛮多的,详见代码吧。


代码:

  • #include <cstdio>

  • #include <algorithm>

  • #include <cstring>

  • #include <vector>

  • #include <cmath>

  •   

  • using namespace std ;

  •   

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

  • #define clear( x ) memset( x , 0 , sizeof( x ) )

  • #define DOWN( i , r , l ) for ( int i = r ; i >= l ; -- i )

  •   

  • const int maxn = 10100 , inf = 0x7fffffff , maxm = 1010000 , maxs = 110 ;

  • const double esp = 0.000000001 ;

  •   

  • struct edge {

  •     int t ;

  •     edge *next ;

  • } E[ maxm << 1 ] ;

  •   

  • edge *pt = E ;

  •   

  • struct graph {

  •       

  •     edge *head[ maxn ] ;

  •       

  •     graph(  ) {

  •         clear( head ) ;

  •     }

  •       

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

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

  •         head[ s ] = pt ++ ;

  •     }

  •       

  • } G , g ;

  •   

  • #define travel( x , X ) for ( edge *p = X.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 )

  •   

  • int N , M , S , T , d[ maxn ] ;

  •   

  • bool Used[ maxn ] , used[ maxn ] ;

  •   

  • void Dfs( int now ) {

  •     Used[ now ] = true ;

  •     travel( now , G ) if ( ! Used[ p -> t ] ) {

  •         Dfs( p -> t ) ;

  •     }

  • }

  •   

  • void dfs( int now ) {

  •     used[ now ] = true ;

  •     travel( now , g ) if ( ! used[ p -> t ] ) {

  •         dfs( p -> t ) ;

  •     }

  • }

  •   

  • int dfn[ maxn ] , low[ maxn ] , id[ maxn ] , cnt = 0 ;

  • vector < int > scc[ maxn ] ;

  • double del[ maxn ] ;

  • int Sta[ maxn ] , Top = 0 , num[ maxn ] ;

  •   

  • void tarjan( int now ) {

  •     dfn[ now ] = low[ now ] = ++ cnt , used[ Sta[ ++ Top ] = now ] = true ;

  •     travel( now , G ) if ( ! dfn[ p -> t ] ) {

  •         tarjan( p -> t ) ;

  •         low[ now ] = min( low[ now ] , low[ p -> t ] ) ;

  •     } else if ( used[ p -> t ] ) low[ now ] = min( low[ now ] , dfn[ p -> t ] ) ;

  •     if ( dfn[ now ] == low[ now ] ) {

  •         int v ;

  •         do {

  •             used[ v = Sta[ Top -- ] ] = false , num[ v ] = scc[ now ].size(  ) ;

  •             scc[ id[ v ] = now ].push_back( v ) ;

  •         } while ( v != now ) ;

  •     }

  • }

  •   

  • int D[ maxn ] ;

  •   

  • double mat[ maxs ][ maxs ] , res[ maxs ] ;

  •   

  • inline void gause( int n ) {

  •     Rep( i , n ) {

  •         int ret = i ;

  •         REP( j , ( i + 1 ) , ( n - 1 ) ) if ( abs( mat[ j ][ i ] ) > abs( mat[ ret ][ i ] ) ) {

  •             ret = j ;

  •         }

  •         if ( ret != i ) REP( j , 0 , n ) swap( mat[ i ][ j ] , mat[ ret ][ j ] ) ;

  •         REP( j , ( i + 1 ) , ( n - 1 ) ) {

  •             double mul = mat[ j ][ i ] / mat[ i ][ i ] ;

  •             REP( k , 0 , n ) mat[ j ][ k ] -= mul * mat[ i ][ k ] ;

  •         }

  •     }

  •     DOWN( i , ( n - 1 ) , 0 ) {

  •         res[ i ] = mat[ i ][ n ] / mat[ i ][ i ] ;

  •         DOWN( j , ( i - 1 ) , 0 ) mat[ j ][ n ] -= mat[ j ][ i ] * res[ i ] ;

  •     }

  • }

  •   

  • int main(  ) {

  •     scanf( "%d%d%d%d" , &N , &M , &S , &T ) ;

  •     for ( int s , t ; M -- ; ) {

  •         scanf( "%d%d" , &s , &t ) ;

  •         G.addedge( s , t ) , g.addedge( t , s ) , ++ d[ s ] ;

  •     }

  •     clear( Used ) , clear( used ) ;

  •     Dfs( S ) , dfs( T ) ;

  •     rep( i , N ) if ( Used[ i ] && ! used[ i ] ) {

  •         printf( "INF\n" ) ; return 0 ;

  •     }

  •     clear( dfn ) , clear( used ) ;

  •     rep( i , N ) if ( ! dfn[ i ] ) tarjan( i ) ;

  •     clear( D ) ;

  •     rep( i , N ) travel( i , g ) if ( id[ i ] != id[ p -> t ] ) {

  •         ++ D[ id[ p -> t ] ] ;

  •     }

  •     clear( del ) , clear( used ) ; used[ id[ T ] ] = true ;

  •     Top = 0 ;

  •     rep( i , N ) if ( i == id[ i ] && ! D[ i ] ) {

  •         Sta[ ++ Top ] = i ;

  •     }

  •     for ( int now ; Top ; ) {

  •         now = Sta[ Top -- ] ;

  •         if ( used[ now ] ) {

  •             int s = scc[ now ].size(  ) ;

  •             REP( i , 0 , s ) REP( j , 0 , s ) {

  •                 mat[ i ][ j ] = 0 ;

  •             }

  •             Rep( i , s ) {

  •                 int v = scc[ now ][ i ] ;

  •                 if ( v == T ) {

  •                     mat[ i ][ i ] = 1 , mat[ i ][ s ] = 0 ;

  •                     continue ;

  •                 }

  •                 mat[ i ][ i ] += - double( d[ v ] ) , mat[ i ][ s ] += - del[ v ] * double( d[ v ] ) ;

  •                 travel( v , G ) if ( id[ v ] == id[ p -> t ] ) {

  •                     mat[ i ][ num[ p -> t ] ] += 1.0 , mat[ i ][ s ] -= 1.0 ;

  •                 }

  •             }

  •             gause( s ) ;

  •             Rep( i , s ) {

  •                 int v = scc[ now ][ i ] ;

  •                 del[ v ] = res[ i ] ;

  •                 travel( v , g ) if ( id[ p -> t ] != now ) {

  •                     del[ p -> t ] += ( del[ v ] + 1 ) / double( d[ p -> t ] ) ;

  •                     used[ id[ p -> t ] ] = true ;

  •                 }

  •             }

  •         }

  •         Rep( i , scc[ now ].size(  ) ) {

  •             int v = scc[ now ][ i ] ;

  •             travel( v , g ) if ( id[ p -> t ] != now ) {

  •                 if ( ! ( -- D[ id[ p -> t ] ] ) ) Sta[ ++ Top ] = id[ p -> t ] ;

  •             }

  •         }

  •     }

  •     printf( "%.3f\n" , del[ S ] + esp ) ;

  •     return 0 ;



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

历史上的今天

评论

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

页脚

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