Cod sursa(job #544305)

Utilizator radu_voroneanuVoroneanu Radu Stefan radu_voroneanu Data 1 martie 2011 13:18:58
Problema Pixels Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.55 kb
#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

#define MAXN 105
#define INF 1000000000

vector<int> G[MAXN*MAXN], Cap[MAXN*MAXN];
bool Viz[MAXN*MAXN];
int flow[MAXN*MAXN];
int Ant[MAXN*MAXN];
int Q[MAXN*MAXN];
int S,D;
bool ok;
int i,j,N,k,x,flu;
int dirx[4] = {-1,0,1,0};
int diry[4] = {0,1,0,-1};

inline void add_arc(const int &x, const int &y, const int &c)
{
	G[x].push_back(y);
	Cap[x].push_back(c);
}

inline int indice(const int &nod, const int &caut)
{
	if (nod == S) return caut-1;
	if (nod == D) return caut-1;
	int i;
	for (i = 0; i< G[nod].size(); ++i)
		if (G[nod][i] == caut)
			return i;
}

inline bool bfs()
{
	int t,nr,i;
	int nod, nod2, x;
	memset(Viz, false, sizeof(Viz));
	memset(flow, 0, sizeof(flow));
	memset(Ant, -1, sizeof(Ant));
	
	Q[0] = S;
	nr = 0;
	Viz[S] = true;
	flow[S] = INF;
	for (t=0; t<=nr; ++t){
		nod = Q[t];
		for (i=0; i<G[nod].size(); ++i){
			nod2 = G[nod][i];
			x = Cap[nod][i];
			if (!Viz[nod2] && x > 0){
				flow[nod2] = min(x, flow[nod]);
				Ant[nod2] = nod;
				Viz[nod2] = true;
				Q[++nr] = nod2;
			}
		}
	}
	if (Viz[D] && flow[D])
		return true;
	return false;
}

inline void flux()
{
	int i,nod,r,poz,poz2;
	ok = false;
	for (i=0; i<G[D].size(); ++i){
		nod = G[D][i];
		poz = indice(nod, D);
		r = Cap[nod][poz];
		
		if (r == 0) continue;
		
		for (j=nod; j!=S; j=Ant[j]){
			poz2 = indice(Ant[j], j);
			r = min(r, Cap[Ant[j]][poz2]);
		}
		
		if (r==0) continue;
		
		for (j=nod; j!=S; j=Ant[j]){
			poz2 = indice(j, Ant[j]);
			Cap[j][poz2] += r;
			poz2 = indice(Ant[j], j);
			Cap[Ant[j]][poz2] -= r;
		}
		
		Cap[nod][poz] -= r;
		Cap[D][i] += r;
		
		flu -= r;
		ok = true;
	}
}

inline int f(const int &x, const int &y)
{ return ((x-1)*N+y); }

int main()
{
	freopen("pixels.in","r",stdin);
	freopen("pixels.out","w",stdout);
	
	scanf("%d",&N);
	S = 0; D = N*N+1;
	for (i=1; i<=N; ++i)
		for (j=1; j<=N; ++j){
			scanf("%d",&x);
			flu += x;
			add_arc(S, f(i,j), x);
			add_arc(f(i,j), S, x);
		}
	
	for (i=1; i<=N; ++i)
		for (j=1; j<=N; ++j){
			scanf("%d",&x);
			flu += x;
			add_arc(D, f(i,j), x);
			add_arc(f(i,j), D, x);
		}
			
	for (i=1; i<=N; ++i)
		for (j=1; j<=N; ++j)
			for (k=0; k<4; ++k){
				scanf("%d",&x);
				if (i+dirx[k] < 1 || j+diry[k]<1) continue;
				if (i+dirx[k] > N || j+diry[k]>N) continue;
				add_arc(f(i,j), f(i+dirx[k], j+diry[k]), x);
			}
			
	while (bfs()){
		flux();
		if (ok==false) break;
	}
	
	printf("%d\n", flu);
	
	return 0;
}