BZOJ-2208: [Jsoi2010]连通数（Tarjan缩

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

首先暴力搞是不行的，复杂度O(n^3)稳TLE，考虑到是一个有向图，就先用Tarjan算法缩强连通分量，处理成一个拓扑图，然后拓扑排序，过程中顺便转移状态（据说位运算+状压可以加速，不过直接bitset也慢不到哪里去就是了。。。）开始忘记处理重边Wa了半天，最后干脆删了拓扑排序直接DFS居然还过了。。。数据太弱了。。。

代码（Tarjan缩SCC+拓扑排序）：

5bafa40f4bfbfbed68f82d1c7af0f736afc31f2b.jpg.png

#include <cstdio>

#include <algorithm>
#include <cstring>
#include <stack>
#include <bitset>
   
using namespace std ;
   
#define MAXN 2010
   
void getstr( char *s ) {
    int ch , len = 0 ;
    for ( ch = getchar(  ) ; ! ( ch == '0' || ch == '1' ) ; ch = getchar(  ) ) ;
    s[ ++ len ] = ch ;
    for ( ch = getchar(  ) ; ch == '0' || ch == '1' ; ch = getchar(  ) ) s[ ++ len ] = ch ;
}
   
struct edge {
    edge *next ; 
    int t ;
} *head[ MAXN ] ;
   
int pre[ MAXN ] ;
   
void AddEdge( int s , int t ) {
    edge *p = new( edge ) ;
    p -> t = t , p -> next = head[ s ] ;
    head[ s ] = p ;
    ++ pre[ t ] ;
}
   
int n ;
char s[ MAXN ][ MAXN ] ;
   
int dfn[ MAXN ] , low[ MAXN ] , size[ MAXN ] , scc[ MAXN ] , cnt = 0 ;
bool f[ MAXN ] ;
stack < int > S ;
   
void Tarjan( int v ) {
    dfn[ v ] = low[ v ] = ++ cnt ;
    S.push( v ) , f[ v ] = true ;
    for ( edge *p = head[ v ] ; p ; p = p -> next ) if ( ! dfn[ p -> t ] ) {
        Tarjan( p -> t ) ; low[ v ] = min( low[ v ] , low[ p -> t ] ) ;
    } else if ( f[ p -> t ] ) low[ v ] = min( low[ v ] ,low[ p -> t ] ) ;
    if ( dfn[ v ] == low[ v ] ) {
        int u ;
        do {
            u = S.top(  ) ; S.pop(  ) , f[ u ] = false ;
            scc[ u ] = v , ++ size[ v ] ;
        } while ( u != v ) ;
    }
}
   
int ans = 0 ;
bitset < MAXN > w[ MAXN ] ;
bool flag[ MAXN ][ MAXN ] ;
   
int main(  ) {
    scanf( "%d" , &n ) ; for ( int i = 0 ; i ++ < n ; ) getstr( s[ i ] ) ;
    memset( head , 0 , sizeof( head ) ) ;
    for ( int i = 0 ; i ++ < n ; ) for ( int j = 0 ; j ++ < n ; ) {
        if ( s[ i ][ j ] == '1' ) AddEdge( i , j ) ;
    }
    memset( dfn , 0 , sizeof( dfn ) ) ;
    memset( size , 0 , sizeof( size ) ) ;
    memset( f , false , sizeof( f ) ) ;
    for ( int i = 0 ; i ++ < n ; ) if ( ! dfn[ i ] ) {
        Tarjan( i ) ;
    }
    memset( head , 0 , sizeof( head ) ) ;
    memset( flag , true , sizeof( flag ) ) ;
    memset( pre , 0 , sizeof( pre ) ) ;
    for ( int i = 0 ; i ++ < n ; ) for ( int j = 0 ; j ++ < n ; ) if ( scc[ i ] != scc[ j ] ) {
        if ( s[ i ][ j ] == '1' && flag[ scc[ i ] ][ scc[ j ] ] ) AddEdge( scc[ i ] , scc[ j ] ) , flag[ scc[ i ] ][ scc[ j ] ] = false ;
    }
    while ( S.size(  ) ) S.pop(  ) ;
    for ( int i = 0 ; i ++ < n ; ) if ( i == scc[ i ] && ! pre[ i ] ) {
        S.push( i ) ;
    }
    for ( int i = 0 ; i ++ < n ; ) if ( i == scc[ i ] ) w[ i ].reset(  ) , w[ i ][ i ] = true ;
    while ( ! S.empty(  ) ) {
        int v = S.top(  ) ; S.pop(  ) ;
        for ( int i = 0 ; i ++ < n ; ) if ( w[ v ][ i ] ) ans += size[ v ] * size[ i ] ;
        for ( edge *p = head[ v ] ; p ; p = p -> next ) {
            if ( ! ( -- pre[ p -> t ] ) ) S.push( p -> t ) ;
            w[ p -> t ] |= w[ v ] ;
        }
    }
    printf( "%d\n" , ans ) ;
    return 0 ;
}