Pagini recente » Cod sursa (job #313022) | Cod sursa (job #1194913) | Cod sursa (job #836885) | Cod sursa (job #72784) | Cod sursa (job #910937)
Cod sursa(job #910937)
#include<stdio.h>
#include<vector>
#define maxn 10005
#define inf (1<<29)
using namespace std;
FILE*f=fopen("pixels.in","r");
FILE*g=fopen("pixels.out","w");
int n,m,S,D,sol;
int T[maxn],viz[maxn],C[maxn];
vector<int>G[maxn];
struct edge{
int vecin;
int f,cap;
int opus;
}M[8*maxn];
inline void baga ( int x , int y , int c1 , int c2 ){
++m;
M[m].vecin = y; M[m].cap = c1;
M[m].opus = m+1;
G[x].push_back(m);
++m;
M[m].vecin = x; M[m].cap = c2;
M[m].opus = m-1;
G[y].push_back(m);
}
inline bool BFS () {
for ( int i = 1 ; i <= n ; ++i ){
viz[i] = 0;
}
int ok = 0;
int p = 1,u = 0;
C[++u] = S; viz[S] = 1;
while ( p <= u ){
int nod = C[p];
for ( vector<int>::iterator itt = G[nod].begin() ; itt != G[nod].end() ; ++itt ){
int mch = (*itt);
if ( M[mch].cap > M[mch].f ){
int vecin = M[mch].vecin;
if ( vecin == D ){
ok = 1; continue ;
}
if ( !viz[vecin] ){
T[vecin] = mch;
C[++u] = vecin; viz[vecin] = 1;
}
}
}
++p;
}
return ok;
}
inline void flux () {
while ( BFS() ){
for ( vector<int>::iterator itt = G[D].begin() ; itt != G[D].end() ; ++itt ){
int mch = (*itt);
T[D] = M[mch].opus;
int nod,minim = inf;
for ( nod = D ; T[nod] ; nod = M[M[T[nod]].opus].vecin ){
minim = min(minim,M[T[nod]].cap-M[T[nod]].f);
}
if ( nod != S ) continue ;
for ( nod = D ; T[nod] ; nod = M[M[T[nod]].opus].vecin ){
M[T[nod]].f += minim;
M[M[T[nod]].opus].f -= minim;
}
sol -= minim;
}
}
}
int main () {
fscanf(f,"%d",&n);
S = n*n+1; D = n*n+2;
int cost;
for ( int i = 1 ; i <= n ; ++i ){
for ( int j = 1 ; j <= n ; ++j ){
fscanf(f,"%d",&cost);
baga(S,(i-1)*n+j,cost,0);
sol += cost;
}
}
for ( int i = 1 ; i <= n ; ++i ){
for ( int j = 1 ; j <= n ; ++j ){
fscanf(f,"%d",&cost);
baga((i-1)*n+j,D,cost,0);
sol += cost;
}
}
for ( int i = 1 ; i <= n ; ++i ){
for ( int j = 1 ; j <= n ; ++j ){
int c1,c2,c3,c4;
fscanf(f,"%d %d %d %d",&c1,&c2,&c3,&c4);
if ( j != n ){
baga((i-1)*n+j,(i-1)*n+j+1,c2,c2);
}
if ( i != n ){
baga((i-1)*n+j,i*n+j,c3,c3);
}
}
}
n = n*n+2;
flux();
fprintf(g,"%d\n",sol);
fclose(f);
fclose(g);
return 0;
}