Cod sursa(job #544335)

Utilizator freak93Adrian Budau freak93 Data 1 martie 2011 14:44:33
Problema Pixels Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.23 kb
#include <fstream>
#include <cstring>
#include <vector>
#include <queue>
#define x first
#define y second

using namespace std;

const char iname[] = "pixels.in";
const char oname[] = "pixels.out";
const int maxn = 105;
const int inf = 0x3f3f3f3f;

ifstream f(iname);
ofstream g(oname);

int S, D, A[maxn * maxn];
vector<pair<int, int> > E[maxn * maxn];

inline bool bfs() {
	queue<int> Q;
	Q.push(S);
	memset(A, -1, sizeof(A));
	A[S] = S;
	while (!Q.empty()) {
		int x = Q.front();
		Q.pop();
		if (x == D)
			continue;
		for (vector<pair<int, int> >::iterator it = E[x].begin(); it != E[x].end(); ++it)
			if (A[it -> x] == -1 && it -> y > 0)
				A[it -> x] = x, Q.push(it -> x);//, fprintf(stderr, "(%d, %d, -> %d) ", x, it -> x, it -> y);
	}
	//fprintf(stderr, "d\n");
	return (A[D] != -1);
}

inline pair<int, int> &muc(int x, int y) {
	if (x == S || x == D)
		return E[x][y];
	for (vector<pair<int, int> >::iterator it = E[x].begin(); it != E[x].end(); ++it)
        if (it -> x == y)
			return *it;
	fprintf(stderr, "%d %d\n", x, y);
	A[-500000000000LL] = 1;
}

int n, i, j, x, s, k, dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int main() {
	f >> n;
	S = n * n;
	D = n * n + 1;
	for (i = 0; i < n; ++i)
		for(j = 0; j < n; ++j)
			f >> x, E[S].push_back(make_pair(i * n + j, x)), s += x;
	for (i = 0; i < n; ++i)
		for (j = 0; j < n; ++j)
			f >> x, E[i * n + j].push_back(make_pair(D, x)), s += x,
			E[D].push_back(make_pair(i * n + j, 0));
	
	for (i = 0; i < n; ++i)
		for (j = 0; j < n; ++j)
			for (k = 0; k < 4; ++k) {
				f >> x;
				if (x == 0)
					continue;
				if (i + dx[k] >= 0 && i + dx[k] < n && j + dy[k] >= 0 && j + dy[k] < n)
					E[i * n + j].push_back(make_pair((i + dx[k]) * n + (j + dy[k]), x));
			}             
	while (bfs())
		for (vector<pair<int, int> >::iterator it = E[D].begin(); it != E[D].end(); ++it) {
			if (A[it -> x] == -1)
				continue;
			A[D] = it -> x;
			int cost = inf;
			for (i = D; i != S; i = A[i])
            	cost = min(cost, muc(A[i], i).y);// fprintf(stderr, "(%d, %d, -> %d)   ", A[i], i, muc(A[i], i).y);
			if (cost == 0)
				continue;
			for (i = D; i != S; i = A[i])
				if (A[i] != S)
					muc(A[i], i).y -= cost, muc(i, A[i]).y += cost;
				else
					muc(A[i], i).y -= cost;
			s -= cost;
		}
	g << s << "\n";
}