Cod sursa(job #910838)

Utilizator mihaipopa12Popa Mihai mihaipopa12 Data 11 martie 2013 09:07:11
Problema Pixels Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.06 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[4*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;
}