Cod sursa(job #561426)

Utilizator tamas_iuliaTamas Iulia tamas_iulia Data 20 martie 2011 13:22:51
Problema Pixels Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.61 kb
#include <stdio.h>
#include <string.h>
#include <vector>
#include <queue>
#define Nmax 105
#define pii pair< int,int >
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define INF 2147000000
using namespace std;

int dx[4]={-1,0,1,0}, dy[4]={0,1,0,-1};
queue< int > Q;
vector< pii > v[Nmax*Nmax];
int prev[Nmax*Nmax];
int N,S,D,sol;

inline int Minim(int x,int y){ return x<y ? x:y;}

void citire(){
    int x,i,j,ii,jj,k;
    scanf("%d",&N);
    S=N*N+2; D=N*N+1;

    for(i=1;i<=N;++i)
        for(j=1;j<=N;++j){
            scanf("%d",&x); sol+=x;
            v[S].pb( mp( (i-1)*N+j , x ) );
        }
    for(i=1;i<=N;++i)
        for(j=1;j<=N;++j){
            scanf("%d",&x); sol+=x;
            v[ (i-1)*N+j ].pb( mp( D, x) );
            v[D].pb( mp( (i-1)*N+j, 0 ) );
        }
    for(i=1;i<=N;++i)
        for(j=1;j<=N;++j)
            for(k=0; k<4; ++k){
                scanf("%d",&x);
                ii=i+dx[k]; jj=j+dy[k];
                if( ii && jj && ii<=N && jj<=N )
                    v[ (i-1)*N+j ].pb( mp ( (ii-1)*N+jj, x) );
            }
}

inline int cap_muchie(int x,int y){
    vector< pii >:: iterator it;
    for( it=v[x].begin(); it!=v[x].end(); ++it)
        if( it->f == y ) return it->s;
    return 0;
}
inline void add_muchie(int x,int y,int val){
    vector< pii >:: iterator it;
    for( it=v[x].begin(); it!=v[x].end(); ++it)
        if( it->f == y ) it->s += val;
}

inline int BF(){
    vector< pii >:: iterator it;
    int x;

    memset(prev,0,sizeof(prev));
    while( ! Q.empty() ) Q.pop();
    Q.push(S); prev[S]=-1;

    while( !Q.empty() ){
        x=Q.front(); Q.pop();
        if( x==D ) return 1;

        for( it=v[x].begin(); it!=v[x].end(); ++it)
            if( !prev[it->f] && it->s ){
                prev[it->f]=x;
                Q.push(it->f);
            }
    }

    return 0;
}

void flux(){
    vector< pii >:: iterator it;
    int fmin,wh;

    while( BF() )
    for(it=v[D].begin(); it!=v[D].end(); ++it)
    if( prev[it->f] ){
        prev[D]=it->f;
        fmin=INF;

        for( wh=D; wh!=S; wh=prev[wh] )
            fmin=Minim(fmin, cap_muchie(prev[wh],wh) );

        for( wh=D; wh!=S; wh=prev[wh] ){
            add_muchie( prev[wh], wh, -fmin);
            if( prev[wh] != S )
                add_muchie( wh, prev[wh], +fmin);
        }

        sol -= fmin;
    }
}

int main(){
    freopen("pixels.in","r",stdin);
    freopen("pixels.out","w",stdout);

    citire();
    flux();

    printf("%d\n",sol);
    fclose(stdin); fclose(stdout);
    return 0;
}