Cod sursa(job #1801621)

Utilizator touristGennady Korotkevich tourist Data 9 noiembrie 2016 13:13:44
Problema Pixels Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.14 kb
#include <bits/stdc++.h>
#define Nmax 105
#define INF 1000000000
#define pb push_back

using namespace std;

int cod[Nmax][Nmax],C[4*Nmax*Nmax],F[4*Nmax*Nmax];
int prvn[Nmax*Nmax],prve[Nmax*Nmax],node[4*Nmax*Nmax];
bool used[Nmax][Nmax];
bool viz[Nmax*Nmax];
int S,D,n,ind,rev[4*Nmax*Nmax];
vector <int> L[Nmax*Nmax];
queue <int> Q;

const int dx[]={-1,0,1, 0};
const int dy[]={0 ,1,0,-1};

inline void add_edge(int x, int y, int cap1, int cap2)
{
    node[++ind]=y; L[x].pb(ind);
    C[ind]=cap1;

    node[++ind]=x; L[y].pb(ind);
    C[ind]=cap2;

    rev[ind]=ind-1; rev[ind-1]=ind;
}

inline bool Bfs()
{
    for(int i=1;i<=D;++i) viz[i]=0;
    viz[S]=1; Q.push(S);
    while(!Q.empty())
    {
        int nod=Q.front(); Q.pop();
        for(auto it : L[nod])
            if(!viz[node[it]] && F[it]<C[it])
            {
                viz[node[it]]=1; Q.push(node[it]);
                prvn[node[it]]=nod; prve[node[it]]=it;
            }
    }
    return viz[D];
}

inline int Flow()
{
    int flow=0,min_flow,i;
    while(Bfs())
    {
        min_flow=INF;
        for(i=D;i!=S;i=prvn[i])
            min_flow=min(min_flow,C[prve[i]]-F[prve[i]]);
        for(i=D;i!=S;i=prvn[i])
        {
            F[prve[i]]+=min_flow;
            F[rev[prve[i]]]-=min_flow;
        }
        flow+=min_flow;
    }
    return flow;
}

int main()
{
    int sol=0;
    int i,j,k,x;
    ifstream cin("pixels.in");
    ofstream cout("pixels.out");
    cin>>n;
    S=0; D=n*n+1;

    for(i=1;i<=n;++i)
        for(j=1;j<=n;++j)
        {
            cin>>x;
            sol+=x;
            cod[i][j]=(i-1)*n+j;
            add_edge(S,cod[i][j],x,0);
        }

    for(i=1;i<=n;++i)
        for(j=1;j<=n;++j)
        {
            cin>>x;
            sol+=x;
            add_edge(cod[i][j],D,x,0);
        }

    for(i=1;i<=n;++i)
        for(j=1;j<=n;++j)
            for(k=0;k<4;++k)
            {
                cin>>x;
                if(k>=1 && k<=2 && cod[i+dx[k]][j+dy[k]])
                    add_edge(cod[i][j],cod[i+dx[k]][j+dy[k]],x,x);
            }

    cout<<sol-Flow();
    return 0;
}