题目：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 ;
}
网友评论