Cod sursa(job #792180)

Utilizator DaNutZ2UuUUBB Bora Dan DaNutZ2UuU Data 26 septembrie 2012 18:06:33
Problema Pixels Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.11 kb
#include <fstream>
#include <cstring>
#include <vector>
#include <queue>
#define x first
#define y second

using namespace std;

const int maxn = 105;
const int inf = 0x3f3f3f3f;

ifstream fin("pixels.in");
ofstream fout("pixels.out");

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);
	}

	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;
	fout<<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() {
	fin >> n;
	S = n * n;
	D = n * n + 1;
	for (i = 0; i < n; ++i)
		for(j = 0; j < n; ++j)
			fin >> 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)
			fin >> 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) {
				fin >> 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);
			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;
		}
	fout << s << "\n";
}