Pagini recente » Cod sursa (job #2756767) | Cod sursa (job #262947) | Cod sursa (job #2669066) | Cod sursa (job #123911) | Cod sursa (job #1801621)
#include <bits/stdc++.h>
#define Nmax 105
#define INF 1000000000
#define pb push_back
using namespace std;
int cod[Nmax][Nmax],C[4*Nmax*Nmax],F[4*Nmax*Nmax];
int prvn[Nmax*Nmax],prve[Nmax*Nmax],node[4*Nmax*Nmax];
bool used[Nmax][Nmax];
bool viz[Nmax*Nmax];
int S,D,n,ind,rev[4*Nmax*Nmax];
vector <int> L[Nmax*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 cap1, int cap2)
{
node[++ind]=y; L[x].pb(ind);
C[ind]=cap1;
node[++ind]=x; L[y].pb(ind);
C[ind]=cap2;
rev[ind]=ind-1; rev[ind-1]=ind;
}
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[node[it]] && F[it]<C[it])
{
viz[node[it]]=1; Q.push(node[it]);
prvn[node[it]]=nod; prve[node[it]]=it;
}
}
return viz[D];
}
inline int Flow()
{
int flow=0,min_flow,i;
while(Bfs())
{
min_flow=INF;
for(i=D;i!=S;i=prvn[i])
min_flow=min(min_flow,C[prve[i]]-F[prve[i]]);
for(i=D;i!=S;i=prvn[i])
{
F[prve[i]]+=min_flow;
F[rev[prve[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,0);
}
for(i=1;i<=n;++i)
for(j=1;j<=n;++j)
{
cin>>x;
sol+=x;
add_edge(cod[i][j],D,x,0);
}
for(i=1;i<=n;++i)
for(j=1;j<=n;++j)
for(k=0;k<4;++k)
{
cin>>x;
if(k>=1 && k<=2 && cod[i+dx[k]][j+dy[k]])
add_edge(cod[i][j],cod[i+dx[k]][j+dy[k]],x,x);
}
cout<<sol-Flow();
return 0;
}