Cod sursa(job #2093035)

Utilizator Bodo171Bogdan Pop Bodo171 Data 22 decembrie 2017 20:11:27
Problema Pixels Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.52 kb
#include <iostream>
#include <fstream>
using namespace std;
const int nmax=105;
int d1[]={-1,0,1,0};
int d2[]={0,1,0,-1};
struct celula
{
    int l,c;
}q[nmax*nmax];
int fl[nmax][nmax][6],c[nmax][nmax][6];
int prc[nmax][nmax];
int li,ci,l1,c1,i,j,n,p,u,lf,cf,k,minfl,flow,sum;
bool bfs()
{
    p=1;u=0;bool ok=0;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
    {
          prc[i][j]=-1;
          if(c[i][j][4]+fl[i][j][4]>0)
         {
           ++u;
           q[u].l=i;
           q[u].c=j;
           prc[i][j]=4;
         }
    }
    while(p<=u)
    {
        li=q[p].l;ci=q[p].c;p++;
        if(fl[li][ci][5]<c[li][ci][5])
        {
            l1=li;c1=ci;
            ok=1;
        }
        for(i=0;i<4;i++)
        {
            lf=li+d1[i];cf=ci+d2[i];
            if(fl[li][ci][i]<c[li][ci][i]&&(prc[lf][cf]==-1))
            {
                prc[lf][cf]=(i^2);
                u++;
                q[u].l=lf;q[u].c=cf;
            }
        }
    }
    return ok;
}
int main()
{
    ifstream f("pixels.in");
    ofstream g("pixels.out");
    f>>n;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
           {
               f>>c[i][j][4];
               sum+=c[i][j][4];
           }
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            {
                f>>c[i][j][5];
                sum+=c[i][j][5];
            }
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
           for(k=0;k<4;k++)
             f>>c[i][j][k];
    while(bfs())
    {
        for(l1=1;l1<=n;l1++)
            for(c1=1;c1<=n;c1++)
                if(c[l1][c1][5]-fl[l1][c1][5]>0&&prc[l1][c1]!=-1)
        {
        li=l1;ci=c1;minfl=c[li][ci][5]-fl[li][ci][5];
        while(ci>0)
        {
            minfl=min(minfl,c[li][ci][prc[li][ci]]+fl[li][ci][prc[li][ci]]);
            if(prc[li][ci]<4)
            {
                lf=li+d1[prc[li][ci]];cf=ci+d2[prc[li][ci]];
            }
            else
            {
                lf=n+1;cf=0;
            }
            li=lf;ci=cf;
        }
        li=l1;ci=c1;fl[li][ci][5]+=minfl;
        while(ci>0)
        {
             fl[li][ci][prc[li][ci]]-=minfl;
             if(prc[li][ci]<4)
            {
                lf=li+d1[prc[li][ci]];cf=ci+d2[prc[li][ci]];
            }
            else
            {
                lf=n+1;cf=0;
            }
            if(cf)fl[lf][cf][(prc[li][ci]^2)]+=minfl;
            li=lf;ci=cf;
        }
        flow+=minfl;
        }
    }
    g<<sum-flow;
    return 0;
}