Pagini recente » Cod sursa (job #2718377) | Cod sursa (job #490413) | Cod sursa (job #23470) | Cod sursa (job #2346201) | Cod sursa (job #2596502)
#include<fstream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
ifstream f("pixels.in");
ofstream g("pixels.out");
struct elem
{
int x,poz;
};
vector<elem>a[10005];
elem tata[10005];
int n,s,d,sol,r[80005];
bool viz[10005];
queue<int>q;
inline bool bfs()
{
int i,x,l;
for(i=1;i<=n;i++)
viz[i]=0,tata[i]={0,0};
q.push(s);
viz[s]=1;
while(!q.empty())
{
x=q.front();
q.pop();
l=a[x].size();
for(i=0;i<l;i++)
if(viz[a[x][i].x]==0&&r[a[x][i].poz]>0)
{
viz[a[x][i].x]=1;
tata[a[x][i].x].x=x;
tata[a[x][i].x].poz=a[x][i].poz;
q.push(a[x][i].x);
}
}
return viz[d];
}
inline void flux_maxim()
{
int i,j,flow,l=a[d].size();
while(bfs()!=0)
{
for(i=0;i<l;i++)
if(tata[a[d][i].x].x!=0&&r[a[d][i].poz^1]>0)
{
flow=r[a[d][i].poz^1];
for(j=a[d][i].x;j!=s;j=tata[j].x)
{
flow=min(flow,r[tata[j].poz]);
if(flow==0)
break;
}
if(flow!=0)
{
r[a[d][i].poz^1]-=flow;
r[a[d][i].poz]+=flow;
for(j=a[d][i].x;j!=s;j=tata[j].x)
{
r[tata[j].poz]-=flow;
r[tata[j].poz^1]+=flow;
}
sol+=flow;
}
}
}
}
int main()
{
int i,j,x,y,c,k=0,SOL=0;
f>>n;
s=n*n+1;
d=n*n+2;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
f>>c;
SOL+=c;
x=(i-1)*n+j;
r[k]=c;
a[s].push_back({x,k});
k++;
r[k]=0;
a[x].push_back({s,k});
k++;
}
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
f>>c;
SOL+=c;
x=(i-1)*n+j;
r[k]=c;
a[x].push_back({d,k});
k++;
r[k]=0;
a[d].push_back({x,k});
k++;
}
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
f>>c;
f>>c;
if(c!=0)
{
x=(i-1)*n+j;
y=(i-1)*n+j+1;
r[k]=c;
a[x].push_back({y,k});
k++;
r[k]=c;
a[y].push_back({x,k});
k++;
}
f>>c;
if(c!=0)
{
x=(i-1)*n+j;
y=i*n+j;
r[k]=c;
a[x].push_back({y,k});
k++;
r[k]=c;
a[y].push_back({x,k});
k++;
}
f>>c;
}
n=n*n+2;
flux_maxim();
SOL-=sol;
g<<SOL;
return 0;
}