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

GreenCloudS

 
 
 

日志

 
 

BZOJ-2668: [cqoi2012]交换棋子(费用流)  

2014-03-11 21:19:00|  分类: 费用流,网络流,bz |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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


建模有点神奇,然后就直接费用流了。


代码:

  • #include <cstdio>

  • #include <algorithm>

  • #include <cstring>

  •  

  • using namespace std ;

  •  

  • #define maxv maxn * maxn *3

  • #define maxn 25

  • #define inf 0x7fffffff

  • #define check( x , y ) ( x >0&& y >0&& x <= n && y <= m )

  •  

  • char s[2][ maxn ][ maxn ], w[ maxn ][ maxn ];

  • int n , m , node[ maxn ][ maxn ][3], V =0;

  •  

  • struct network{

  •     

  •     struct edge{

  •         edge *next ,*pair ;

  •         int t , f , c ;

  •     }*head[ maxv ];

  •     

  •     int S , T ;

  •     

  •     network(  ){

  •         memset( head ,0,sizeof( head ));

  •     }

  •     

  •     void Add(int s ,int t ,int f ,int c ){

  •         edge *p =new( edge );

  •         p -> t = t , p -> f = f , p -> c = c , p -> next = head[ s ];

  •         head[ s ]= p ;

  •     }

  •     

  •     void AddEdge(int s ,int t ,int f ,int c ){

  •         Add( s , t , f , c ),Add( t , s ,0,- c );

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

  •     }

  •     

  •     int dist[ maxv ], slack[ maxv ], Maxflow , Mincost ;

  •     bool f[ maxv ];

  •     

  •     int aug(int v ,int flow ){

  •         if( v == T ){

  •             Maxflow += flow , Mincost += flow * dist[ S ];

  •             return flow ;

  •         }

  •         int rec =0; f[ v ]=false;

  •         for( edge *p = head[ v ]; p ; p = p -> next )if( f[ p -> t ]&& p -> f ){

  •             if( dist[ v ]== dist[ p -> t ]+ p -> c ){

  •                 int ret =aug( p -> t ,min( flow - rec , p -> f ));

  •                 p -> f -= ret , p -> pair -> f += ret ;

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

  •             }else slack[ p -> t ]=min( slack[ p -> t ], dist[ p -> t ]+ p -> c - dist[ v ]);

  •         }

  •         return rec ;

  •     }

  •     

  •     bool relabel(  ){

  •         int delta = inf ;

  •         for(int i =0; i ++< T ;)if( f[ i ]) delta =min( delta , slack[ i ]);

  •         if( delta == inf )return false;

  •         for(int i =0; i ++< T ;)if(! f[ i ]) dist[ i ]+= delta ;

  •         return true;

  •     }

  •     

  •     void costflow(  ){

  •         Maxflow = Mincost =0;

  •         memset( dist ,0,sizeof( dist ));

  •         do{

  •             for(int i =0; i ++< T ;) slack[ i ]= inf ;

  •             do{

  •                 memset( f ,true,sizeof( f ));

  •             }while(aug( S , inf ));

  •         }while(relabel(  ));

  •     }

  •     

  • } net ;

  •  

  • int cnt[2], counter =0;

  •  

  • const int dir[8][2]={{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};

  •  

  • int main(  ){

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

  •     cnt[0]= cnt[1]=0;

  •     for(int i =0; i ++< n ;){

  •         scanf("%s", s[0][ i ]+1);

  •         for(int j =0; j ++< m ;)if( s[0][ i ][ j ]=='1'){

  •             ++ cnt[0];

  •         }

  •     }

  •     for(int i =0; i ++< n ;){

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

  •         for(int j =0; j ++< m ;)if( s[1][ i ][ j ]=='1'){

  •             ++ cnt[1];

  •         }

  •     }

  •     if( cnt[0]!= cnt[1]){

  •         printf("-1\n");return 0;

  •     }

  •     for(int i =0; i ++< n ;)scanf("%s", w[ i ]+1);

  •     for(int i =0; i ++< n ;)for(int j =0; j ++< m ;){

  •         for(int k =0; k <3;++ k ) node[ i ][ j ][ k ]=++ V ;

  •     }

  •     net.S =++ V ; net.T =++ V ;

  •     for(int i =0; i ++< n ;)for(int j =0; j ++< m ;){

  •         if( s[0][ i ][ j ]!= s[1][ i ][ j ]){

  •             if( s[0][ i ][ j ]=='1'){

  •                 ++ counter ;

  •                 net.AddEdge( net.S , node[ i ][ j ][0],1,0);

  •                 net.AddEdge( node[ i ][ j ][0], node[ i ][ j ][2],( w[ i ][ j ]-'0'+1)/2,0);

  •                 net.AddEdge( node[ i ][ j ][1], node[ i ][ j ][0],( w[ i ][ j ]-'0')/2,0);

  •             }else{

  •                 net.AddEdge( node[ i ][ j ][0], net.T ,1,0);

  •                 net.AddEdge( node[ i ][ j ][0], node[ i ][ j ][2],( w[ i ][ j ]-'0')/2,0);

  •                 net.AddEdge( node[ i ][ j ][1], node[ i ][ j ][0],( w[ i ][ j ]-'0'+1)/2,0);

  •             }

  •         }else{

  •             net.AddEdge( node[ i ][ j ][1], node[ i ][ j ][0],( w[ i ][ j ]-'0')/2,0);

  •             net.AddEdge( node[ i ][ j ][0], node[ i ][ j ][2],( w[ i ][ j ]-'0')/2,0);

  •         }

  •         for(int k =0; k <8;++ k ){

  •             int x = i + dir[ k ][0], y = j + dir[ k ][1];

  •             if(check( x , y )){

  •                 net.AddEdge( node[ i ][ j ][2], node[ x ][ y ][1], inf ,1);

  •             }

  •         }

  •     }

  •     net.costflow(  );

  •     if( net.Maxflow < counter )printf("-1\n");else printf("%d\n", net.Mincost );

  •     return 0;

  • }


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

历史上的今天

评论

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

页脚

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