BZOJ-1189: [HNOI2007]紧急疏散evacuat

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

数据这么小，怎么乱搞都可以啦，二分答案，然后拆点最大流判定即可。

代码：

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <queue>

 

using namespace std ;

 

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

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

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

 

const int maxn = 25 ;

const int maxv = 100000 ;

const int maxm = 1010000 ;

const int inf = 0x7fffffff ;

 

struct edge {

    int t , f ;

    edge *next , *pair ;

} E[ maxm ] ;

 

edge *pt , *head[ maxv ] ;

 

inline void Init(  ) {

    pt = E , memset( head , 0 , sizeof( head ) ) ;

}

 

inline void add( int s , int t , int f ) {

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

    head[ s ] = pt ++ ;

}

 

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

    add( s , t , f ) , add( t , s , 0 ) ;

    head[ s ] -> pair = head[ t ] , head[ t ] -> pair = head[ s ] ;

}

 

int h[ maxv ] , gap[ maxv ] , S , T , V = 0 ;

edge *d[ maxv ] ;

 

int sap( int now , int flow ) {

    if ( now == T ) return flow ;

    int rec = 0 , ret ;

    travel( now ) if ( h[ p -> t ] + 1 == h[ now ] ) {

        ret = sap( p -> t , min( flow - rec , p -> f ) ) ;

        p -> f -= ret , p -> pair -> f += ret , d[ now ] = p ;

        if ( ( rec += ret ) == flow ) return flow ;

    }

    if ( ! ( -- gap[ h[ now ] ] ) ) h[ S ] = V ;

    ++ gap[ ++ h[ now ] ] , d[ now ] = head[ now ] ;

    return rec ;

}

 

inline int maxflow(  ) {

    memset( h , 0 , sizeof( h ) ) , memset( gap , 0 , sizeof( gap ) ) ;

    gap[ 0 ] = V ;

    rep( i , V ) d[ i ] = head[ i ] ;

    int flow = 0 ;

    for ( ; h[ S ] < V ; flow += sap( S , inf ) ) ;

    return flow ;

}

 

int n , m , node[ maxn ][ maxn ][ maxn * maxn * 2 ] ;

char s[ maxn ][ maxn ] ;

int dist[ maxn ][ maxn ][ maxn ][ maxn ] , dis[ maxn ][ maxn ] ;

 

queue < pair < int , int > > q ;

 

inline void update( int x , int y , int cost ) {

    if ( s[ x ][ y ] == 'X' ) return ;

    if ( dis[ x ][ y ] > cost ) {

        dis[ x ][ y ] = cost , q.push( make_pair( x , y ) ) ;

    }

}

 

inline void bfs( int x , int y ) {

    while ( ! q.empty(  ) ) q.pop(  ) ;

    rep( i , n ) rep( j , m ) dis[ i ][ j ] = inf ;

    dis[ x ][ y ] = 0 , q.push( make_pair( x , y ) ) ;

    pair < int , int > now ;

    int cost ;

    while ( ! q.empty(  ) ) {

        now = q.front(  ) ; q.pop(  ) ;

        cost = dis[ now.first ][ now.second ] + 1 ;

        if ( now.first > 1 ) update( now.first - 1 , now.second , cost ) ;

        if ( now.first < n ) update( now.first + 1 , now.second , cost ) ;

        if ( now.second > 1 ) update( now.first , now.second - 1 , cost ) ;

        if ( now.second < m ) update( now.first , now.second + 1 , cost ) ;

    }

}

 

inline bool check( int mid ) {

    Init(  ) ;

    V = 0 ;

    rep( i , n ) rep( j , m ) if ( s[ i ][ j ] == '.' ) {

        node[ i ][ j ][ 0 ] = ++ V ;

    } else if ( s[ i ][ j ] == 'D' ) {

        rep( k , mid ) node[ i ][ j ][ k ] = ++ V ;

    }

    S = ++ V , T = ++ V ;

    int cnt = 0 ;

    rep( i , n ) rep( j , m ) if ( s[ i ][ j ] == '.' ) {

        addedge( S , node[ i ][ j ][ 0 ] , 1 ) , ++ cnt ;

        rep( a , n ) rep( b , m ) if ( s[ a ][ b ] == 'D' && dist[ i ][ j ][ a ][ b ] <= mid ) {

            addedge( node[ i ][ j ][ 0 ] , node[ a ][ b ][ dist[ i ][ j ][ a ][ b ] ] , 1 ) ;

        }

    } else if ( s[ i ][ j ] == 'D' ) {

        rep( k , mid ) {

            addedge( node[ i ][ j ][ k ] , T , 1 ) ;

            if ( k < mid ) addedge( node[ i ][ j ][ k ] , node[ i ][ j ][ k + 1 ] , inf ) ;

        }

    }

    return maxflow(  ) == cnt ;

}

 

int main(  ) {

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

    rep( i , n ) scanf( "%s" , s[ i ] + 1 ) ;

    rep( i , n ) rep( j , m ) {

        bfs( i , j ) ;

        rep( a , n ) rep( b , m ) dist[ i ][ j ][ a ][ b ] = dis[ a ][ b ] ;

    }

    int l = -1 , r = n * m * 2 + 1 , mid ;

    while ( r - l > 1 ) {

        mid = ( l + r ) >> 1 ;

        if ( check( mid ) ) r = mid ; else l = mid ;

    }

    if ( r == n * m * 2 + 1 ) printf( "impossible\n" ) ; else printf( "%d\n" , r ) ;

    return 0 ;

}