BZOJ-2707: [SDOI2012]走迷宫(Tarjan求

作者: AmadeusChan | 来源:发表于2019-02-28 14:24 被阅读0次

题目: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 ;

} 

相关文章

  • BZOJ-2707: [SDOI2012]走迷宫(Tarjan求

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

  • 连通图

    Strongly Connected Componenet 割点(tarjan): 题目链接:Network(求割...

  • tarjan-寻找图中有多少个强连通分量

    tarjan寻找图中有多少个强连通分量 hdu 1269 迷宫城堡判断图否是属于一个强连通分量

  • 迷宫问题

    深度优先遍历走迷宫 广度优先遍历走迷宫 代码见github

  • Tarjan算法求割点,桥

    下面介绍中无向图中割点和桥的概念:割点:一个结点称为割点(或者割顶)当且仅当去掉该节点极其相关的边之后的子图不连通...

  • 走迷宫

    今天下雨了,所以外面有很多小水坑,如果踩到水,我的鞋子就会湿了。所以我和妹妹绕着水坑走。我们一会儿往左走,一会儿往...

  • 走迷宫

    我跟弟弟来到了走迷宫地方,我们从入口进去就开始绕。 走这条路不行。就走另一条路。我和弟弟来回绕。最终还是没有出去。...

  • 走迷宫

    今天弟弟到我家来玩,我拿出白棋、黑棋和迷宫地图,我说:“弟弟,我们玩走迷宫吧。”弟弟很快的答应了。 ...

  • 走迷宫

    洗完澡,两个儿子一起高兴地走迷宫,走着走着小儿子突然大声哭起来了。 我问他:“航航,你怎么了?”航航一边擦着鼻涕,...

  • 走迷宫

    坚持分享第521天。 和孩子一起走迷宫,走了几次,她竟爱上了迷宫,每走完孩子就自信满满说:“我帮小熊找到妈...

网友评论

    本文标题:BZOJ-2707: [SDOI2012]走迷宫(Tarjan求

    本文链接:https://www.haomeiwen.com/subject/ifihuqtx.html