Pagini recente » Cod sursa (job #2084794) | Cod sursa (job #1083719) | Cod sursa (job #1154801) | Cod sursa (job #3128925) | Cod sursa (job #2093034)
#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)
{
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;
}