BZOJ-2668:[cqoi 2012]바둑돌 교환(비용 흐름)

제목:http://www.lydsy.com/JudgeOnline/problem.php?id=2668
모델 링 이 좀 신기해 서 바로 비용 이 흘러 요.
코드:

#include 

#include 

#include 

 

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
");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
");else printf("%d
", net.Mincost );

    return 0;

}