Pagini recente » Cod sursa (job #924287) | Cod sursa (job #2769453) | Cod sursa (job #1406156) | Cod sursa (job #338452) | Cod sursa (job #1240635)
#include<fstream>
#include<cstring>
#include<queue>
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
using namespace std;
ifstream in("pixels.in");
ofstream out("pixels.out");
const int Nmax = 150;
const int INF = 0x3f3f3f3f;
int A[Nmax][Nmax],B[Nmax][Nmax];
int N,Cost[Nmax][Nmax][4];
vector<int> G[Nmax*Nmax],C[Nmax*Nmax],I[Nmax*Nmax];
int Sou,Dest;
void addedge(int x,int y,int c){
I[x].push_back(G[y].size());
I[y].push_back(G[x].size());
G[x].push_back(y);
G[y].push_back(x);
C[x].push_back(c);
C[y].push_back(c);
}
int mark[Nmax*Nmax];
int pred[Nmax*Nmax];
queue<int> q;
int bfs(){
memset(mark,0,sizeof(mark));
q.push(Sou); mark[Sou]=1,pred[Sou]=Sou;
while(!q.empty()){
int x=q.front(); q.pop();
for(int i=0;i<G[x].size();i++){
if(!mark[G[x][i]] && C[x][i]>0){
mark[G[x][i]]=i+1;
pred[G[x][i]]=x;
q.push(G[x][i]);
}
}
}
return mark[Dest]>0;
}
int addpath(int x){
int much,ipos,p=x;
for(int i=0;i<G[x].size();i++) if(G[x][i]==Dest) ipos=i;
much=C[x][ipos];
while(p!=Sou){
// pred[p] -> p
much = min( much , C[ pred[p] ][ (mark[p]-1) ] );
p=pred[p];
}
if(!much) return 0;
C[x][ipos] -= much;
C[Dest][ I[x][ipos] ] += much;
p=x;
while(p!=Sou){
C[pred[p]][(mark[p]-1)] -= much;
C[p][ I[pred[p]][(mark[p]-1)] ] += much;
p=pred[p];
}
return much;
}
int code(int x,int y){
return (x-1)*N+y;
}
int main(){
in>>N;
int s=0;
for(int i=1;i<=N;i++) for(int j=1;j<=N;j++) in>>A[i][j],s+=A[i][j];
for(int i=1;i<=N;i++) for(int j=1;j<=N;j++) in>>B[i][j],s+=B[i][j];
for(int i=1;i<=N;i++) for(int j=1;j<=N;j++) for(int k=0;k<=3;k++) in>>Cost[i][j][k];
Sou=N*N+1,Dest=N*N+2;
for(int i=1;i<=N;i++) for(int j=1;j<=N;j++) addedge(Sou,code(i,j),A[i][j]);
for(int i=1;i<=N;i++) for(int j=1;j<=N;j++) addedge(code(i,j),Dest,B[i][j]);
for(int i=1;i<=N;i++) for(int j=1;j<=N;j++){
if(i>1) addedge(code(i,j),code(i-1,j),Cost[i][j][0]);
if(j>1) addedge(code(i,j),code(i,j-1),Cost[i][j][3]);
}
while(bfs()){
for(int i=1;i<=N;i++) for(int j=1;j<=N;j++) s -= addpath(code(i,j));
}
out<<s<<'\n';
return 0;
}