Cod sursa(job #2489843)

Utilizator Ruxandra985Nanu Ruxandra Laura Ruxandra985 Data 9 noiembrie 2019 12:14:44
Problema Pixels Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.01 kb
#include <bits/stdc++.h>
#define DIMN 10010
#define INF 2000000000
using namespace std;
int s , d , n;
deque <int> dq;
vector < int > v[DIMN];
int dist[DIMN],start[DIMN];
int sto[DIMN] , tos[DIMN] , tod[DIMN] , dto[DIMN] , neig[DIMN][4];
int di[]={-1,0,1,0};
int dj[]={0,1,0,-1};
int nr (int i , int j , int n){
    return (i-1) * n + j;
}
int qry (int x , int y){
    int i,j,iv,jv;
    if (x == s)
        return sto[y];
    else if (y == s)
        return tos[x];
    else if (x == d)
        return dto[y];
    else if (y ==  d)
        return tod[x];
    else {
        j = x % n;
        if (!j)
            j = n;
        x-=j;
        i = x / n + 1;
        for (int d = 0; d < 4 ; d++){
            iv = i + di[d];
            jv = j + dj[d];
            if (iv && jv && iv <=n && jv<=n && nr(iv,jv,n) == y){
                return neig[nr(i,j,n)][d];
            }
        }
    }
    return 0;
}
void update (int x , int y , int val){
    int i,j,iv,jv;
    if (x == s)
        sto[y]+=val;
    else if (y == s)
        tos[x]+=val;
    else if (x == d)
        dto[y]+=val;
    else if (y ==  d)
        tod[x]+=val;
    else {
        j = x % n;
        if (!j)
            j = n;
        x-=j;
        i = x / n + 1;
        for (int dir = 0; dir < 4 ; dir++){
            iv = i + di[dir];
            jv = j + dj[dir];
            if (iv && jv && iv <=n && jv<=n && nr(iv,jv,n) == y){
                neig[nr(i,j,n)][dir]+=val;
                return;
            }
        }
    }
}
int bfs (){
    int nod,i,vecin;
    dq.push_back(s);
    memset (dist , 0 , sizeof(dist));
    dist[s] = 1;
    while (!dq.empty()){
        nod = dq.front();
        dq.pop_front();
        for ( i=0 ; i<v[nod].size() ; i++ ){
            vecin = v[nod][i];
            if (!dist[vecin] && qry(nod,vecin)){
                dist[vecin] = dist[nod] + 1;
                dq.push_back(vecin);
            }
        }
    }
    if (dist[d] == 0)
        return 0;
    return 1;
}

int dfs (int nod , int flow){
    int vecin,sol;
    if (nod == d || !flow)
        return flow;

    for (;start[nod] < v[nod].size() ; start[nod]++){
        vecin = v[nod][start[nod]];
        if (dist[nod] + 1 == dist[vecin] && qry(nod,vecin)>=0){
            sol = dfs (vecin , min(flow , qry(nod,vecin)));
            if (sol > 0){
                update(nod,vecin,-sol);
                update(vecin,nod,sol);
                return sol;
            }
        }
    }
    return 0;
}
int main()
{
    FILE *fin = fopen ("pixels.in","r");
    FILE *fout = fopen ("pixels.out","w");
    int q,i,j,a,b,c,dir,mflow,flow,iv,jv;
    fscanf (fin,"%d",&n);
    q = 0;
    s = 0;
    d = n * n + 1;
    for (i=1;i<=n;i++){
        for (j=1;j<=n;j++){
            fscanf (fin,"%d",&a);
            q+=a;
            v[s].push_back(nr(i,j,n));
            v[nr(i,j,n)].push_back(s);
            sto[nr(i,j,n)] = a; /// de la sursa la aia
        }
    }
    for (i=1;i<=n;i++){
        for (j=1;j<=n;j++){
            fscanf (fin,"%d",&b);
            q+=b;
            v[d].push_back(nr(i,j,n));
            v[nr(i,j,n)].push_back(d);
            tod [nr(i,j,n)] = b; /// de la aia la d
        }
    }
    for (i=1;i<=n;i++){
        for (j=1;j<=n;j++){
            for (dir=0;dir<4;dir++){
                fscanf (fin,"%d",&c);
                iv = i + di[dir];
                jv = j + dj[dir];
                if (iv && jv && iv <= n && jv <= n){ /// e un cost valid
                    v[nr(iv,jv,n)].push_back(nr(i,j,n));
                    v[nr(i,j,n)].push_back(nr(iv,jv,n));
                    neig[nr(i,j,n)][dir] = c;
                }
            }
        }
    }
    /// flux pe reteaua aia
    mflow = 0;

    while (bfs()){

        memset (start , 0, sizeof(start));

        flow = dfs (s,INF);

        while (flow > 0){
            mflow += flow;
            flow = dfs(s,INF);
        }

    }

    fprintf (fout,"%d" , q - mflow);
    return 0;
}