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

GreenCloudS

 
 
 

日志

 
 

BZOJ-2150: 部落战争(二分图匹配)  

2014-03-06 20:26:00|  分类: oi,bzoj,二分图匹 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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


赤裸裸的一道最小路径覆盖,直接上匈牙利或网络流即可。


代码:

  • #include <cstdio>
  • #include <algorithm>
  • #include <cstring>
  • #include <bitset>
  •  
  • using namespace std ;
  •  
  • #define maxv maxn * maxn
  • #define maxn 51
  • #define check( x , y ) ( x > 0 && y > 0 && x <= n && y <= m && s[ x ][ y ] == '.' )
  •  
  • struct Match {
  •  
  •     struct edge {
  •         int t ;
  •         edge *next ;
  •     } *head[ maxv ] ;
  •  
  •     int match[ maxv ] ;
  •     bitset < maxv > used ;
  •  
  •     Match(  ) {
  •         memset( head , 0 , sizeof( head ) ) ;
  •         memset( match , 0 , sizeof( match ) ) ;
  •     }
  •  
  •     void AddEdge( int s , int t ) {
  •         edge *p = new( edge ) ;
  •         p -> t = t , p -> next = head[ s ] ; 
  •         head[ s ] = p ;
  •     }
  •  
  •     bool dfs( int v ) {
  •         for ( edge *p = head[ v ] ; p ; p = p -> next ) if ( ! used[ p -> t ] ) {
  •             used[ p -> t ] = true ;
  •             if ( ! match[ p -> t ] || dfs( match[ p -> t ] ) ) {
  •                 match[ p -> t ] = v ; 
  •                 return true ;
  •             }
  •         }
  •         return false ;
  •     }
  •  
  •     int max_match( int v ) {
  •         int cnt = 0 ; 
  •         for ( int i = 0 ; i ++ < v ; ) {
  •             used.reset(  ) ;
  •             if ( dfs( i ) ) ++ cnt ;
  •         }
  •         return cnt ;
  •     }
  •  
  • } mat ;
  •  
  • int node[ maxn ][ maxn ] , n , m , V = 0 , r , c ;
  • char s[ maxn ][ maxn ] ;
  •  
  • int main(  ) {
  •     scanf( "%d%d%d%d" , &n , &m , &r , &c ) ;
  •     for ( int i = 0 ; i ++ < n ; ) {
  •         scanf( "%s" , s[ i ] + 1 ) ;
  •         for ( int j = 0 ; j ++ < m ; ) if ( s[ i ][ j ] == '.' ) {
  •             node[ i ][ j ] = ++ V ;
  •         }
  •     }
  •     for ( int i = 0 ; i ++ < n ; ) for ( int j = 0 ; j ++ < m ; ) if ( s[ i ][ j ] == '.' ) {
  •         int x = i + r , y = j + c ;
  •         if ( check( x , y ) ) mat.AddEdge( node[ i ][ j ] , node[ x ][ y ] ) ;
  •         x = i + r , y = j - c ;
  •         if ( check( x , y ) ) mat.AddEdge( node[ i ][ j ] , node[ x ][ y ] ) ;
  •         x = i + c , y = j + r ;
  •         if ( check( x , y ) ) mat.AddEdge( node[ i ][ j ] , node[ x ][ y ] ) ;
  •         x = i + c , y = j - r ;
  •         if ( check( x , y ) ) mat.AddEdge( node[ i ][ j ] , node[ x ][ y ] ) ;
  •     }
  •     printf( "%d\n" , V - mat.max_match( V ) ) ;
  •     return 0 ; 
  • }



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

历史上的今天

评论

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

页脚

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