Cod sursa(job #1801588)

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

using namespace std;

int cod[Nmax][Nmax],C[Nmax][Nmax],F[Nmax][Nmax],prv[Nmax];
bool viz[Nmax];
int S,D,n;
vector <int> L[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 cap)
{
    L[x].pb(y); C[x][y]=cap;
}

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[it] && F[nod][it]<C[nod][it])
            {
                viz[it]=1; Q.push(it);
                prv[it]=nod;
            }
    }
    return viz[D];
}

inline int Flow()
{
    int flow=0,min_flow,i;
    while(Bfs())
    {
        min_flow=INF;
        for(i=D;i!=S;i=prv[i])
            min_flow=min(min_flow,C[prv[i]][i]-F[prv[i]][i]);
        for(i=D;i!=S;i=prv[i])
        {
            F[prv[i]][i]+=min_flow;
            F[i][prv[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);
            add_edge(cod[i][j],S,0);
        }

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

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

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