Pagini recente » Cod sursa (job #2044865) | Cod sursa (job #1987009) | Cod sursa (job #2523134) | Cod sursa (job #364130) | Cod sursa (job #1801588)
#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;
}