题目：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;
}
网友评论