Cod sursa(job #910282)

Utilizator mihaipopa12Popa Mihai mihaipopa12 Data 10 martie 2013 19:47:46
Problema Pixels Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.21 kb
#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[4*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;
}