Cod sursa(job #910937)

Utilizator mihaipopa12Popa Mihai mihaipopa12 Data 11 martie 2013 10:42:38
Problema Pixels Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.86 kb
#include<stdio.h>
#include<vector>

#define maxn 10005
#define inf (1<<29)

using namespace std;

FILE*f=fopen("pixels.in","r");
FILE*g=fopen("pixels.out","w");

int n,m,S,D,sol;
int T[maxn],viz[maxn],C[maxn];
vector<int>G[maxn];

struct edge{
    int vecin;
    int f,cap;
    int opus;
}M[8*maxn];

inline void baga ( int x , int y , int c1 , int c2 ){

    ++m;
    M[m].vecin = y; M[m].cap = c1;
    M[m].opus = m+1;
    G[x].push_back(m);

    ++m;
    M[m].vecin = x; M[m].cap = c2;
    M[m].opus = m-1;
    G[y].push_back(m);
}

inline bool BFS () {

    for ( int i = 1 ; i <= n ; ++i ){
        viz[i] = 0;
    }

    int ok = 0;
    int p = 1,u = 0;
    C[++u] = S; viz[S] = 1;
    while ( p <= u ){
        int nod = C[p];

        for ( vector<int>::iterator itt = G[nod].begin() ; itt != G[nod].end() ; ++itt ){
            int mch = (*itt);

            if ( M[mch].cap > M[mch].f ){
                int vecin = M[mch].vecin;

                if ( vecin == D ){
                    ok = 1; continue ;
                }

                if ( !viz[vecin] ){
                    T[vecin] = mch;
                    C[++u] = vecin; viz[vecin] = 1;
                }
            }
        }

        ++p;
    }

    return ok;
}

inline void flux () {

    while ( BFS() ){

        for ( vector<int>::iterator itt = G[D].begin() ; itt != G[D].end() ; ++itt ){
            int mch = (*itt);
            T[D] = M[mch].opus;

            int nod,minim = inf;
            for ( nod = D ; T[nod] ; nod = M[M[T[nod]].opus].vecin ){
                minim = min(minim,M[T[nod]].cap-M[T[nod]].f);
            }

            if ( nod != S ) continue ;

            for ( nod = D ; T[nod] ; nod = M[M[T[nod]].opus].vecin ){
                M[T[nod]].f += minim;
                M[M[T[nod]].opus].f -= minim;
            }
            sol -= minim;
        }
    }
}

int main () {

    fscanf(f,"%d",&n);
    S = n*n+1; D = n*n+2;

    int cost;
    for ( int i = 1 ; i <= n ; ++i ){
        for ( int j = 1 ; j <= n ; ++j ){
            fscanf(f,"%d",&cost);
            baga(S,(i-1)*n+j,cost,0);
            sol += cost;
        }
    }
    for ( int i = 1 ; i <= n ; ++i ){
        for ( int j = 1 ; j <= n ; ++j ){
            fscanf(f,"%d",&cost);
            baga((i-1)*n+j,D,cost,0);
            sol += cost;
        }
    }

    for ( int i = 1 ; i <= n ; ++i ){
        for ( int j = 1 ; j <= n ; ++j ){
            int c1,c2,c3,c4;
            fscanf(f,"%d %d %d %d",&c1,&c2,&c3,&c4);

            if ( j != n ){
                baga((i-1)*n+j,(i-1)*n+j+1,c2,c2);
            }
            if ( i != n ){
                baga((i-1)*n+j,i*n+j,c3,c3);
            }
        }
    }

    n = n*n+2;
    flux();

    fprintf(g,"%d\n",sol);

    fclose(f);
    fclose(g);

    return 0;
}