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

GreenCloudS

 
 
 

日志

 
 

BZOJ-1189: [HNOI2007]紧急疏散evacuate(最大流+二分)  

2014-06-09 22:04:00|  分类: oi,bzoj,网络流, |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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



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

历史上的今天

评论

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

页脚

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