Pagini recente » Cod sursa (job #1912674) | Cod sursa (job #49163) | Cod sursa (job #2910796) | Cod sursa (job #561426)
Cod sursa(job #561426)
#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;
}