Cod sursa(job #1240635)

Utilizator teoionescuIonescu Teodor teoionescu Data 11 octombrie 2014 19:51:48
Problema Pixels Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.35 kb
#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;
}