Cod sursa(job #1900846)

Utilizator iordache.bogdanIordache Ioan-Bogdan iordache.bogdan Data 3 martie 2017 16:56:16
Problema Pixels Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.62 kb
#include <fstream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <queue>

const int kMaxDim = 105;

struct Edge {
	int from, to, capacity;
};

int a[kMaxDim][kMaxDim], b[kMaxDim][kMaxDim], c[kMaxDim][kMaxDim][4], nodeTag[kMaxDim][kMaxDim];

int edgeCount;
Edge edges[10 * kMaxDim * kMaxDim];
std::vector< int > adjList[kMaxDim * kMaxDim];

void AddDirectedEdge(int from, int to, int capacity) {
	edges[edgeCount].from = from;
	edges[edgeCount].to = to;
	edges[edgeCount].capacity = capacity;
	edgeCount++;

	adjList[from].push_back(edgeCount - 1);

	edges[edgeCount].from = to;
	edges[edgeCount].to = from;
	edges[edgeCount].capacity = 0;
	edgeCount++;

	adjList[to].push_back(edgeCount - 1);
}

void AddUnDirectedEdge(int first, int second, int capacity) {
	edges[edgeCount].from = first;
	edges[edgeCount].to = second;
	edges[edgeCount].capacity = capacity;
	edgeCount++;

	adjList[first].push_back(edgeCount - 1);

	edges[edgeCount].from = second;
	edges[edgeCount].to = first;
	edges[edgeCount].capacity = capacity;
	edgeCount++;

	adjList[second].push_back(edgeCount - 1);
}

bool visited[kMaxDim * kMaxDim];
int backEdge[kMaxDim * kMaxDim];
std::queue< int > que;

bool Bfs(int source, int destination) {
	memset(visited, false, sizeof visited);

	que.push(source);
	visited[source] = true;

	while (!que.empty()) {
		int curr = que.front();
		que.pop();

		if (curr == destination)
			continue;

		for (int edge : adjList[curr]) {
			if (edges[edge].capacity == 0 || visited[ edges[edge].to ])
				continue;

			backEdge[ edges[edge].to ] = edge;
			visited[ edges[edge].to ] = true;
			que.push( edges[edge].to );
		}
	}

	return visited[destination];
}

int GetMaxFlow(int source, int destination) {
	int maxFlow = 0;
	while (Bfs(source, destination)) {
		for (int finalEdge : adjList[destination]) {
			if (!visited[ edges[finalEdge].to ] || edges[finalEdge ^ 1].capacity == 0)
				continue;

			backEdge[destination] = (finalEdge ^ 1);
			int addFlow = 0x3f3f3f3f;
			for (int node = destination; node != source; node = edges[ backEdge[node] ].from)
				addFlow = std::min(addFlow, edges[ backEdge[node] ].capacity);

			if (addFlow == 0)
				continue;

			maxFlow += addFlow;
			for (int node = destination; node != source; node = edges[ backEdge[node] ].from) {
				edges[ backEdge[node] ].capacity -= addFlow;
				edges[ backEdge[node] ^ 1 ].capacity += addFlow;
			}
		}
	}

	return maxFlow;
}

int main() {
	std::ifstream inputFile("pixels.in");
	std::ofstream outputFile("pixels.out");

	int n;
	inputFile >> n;
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= n; ++j)
			inputFile >> a[i][j];

	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= n; ++j)
			inputFile >> b[i][j];

	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= n; ++j)
			for (int k = 0; k < 4; ++k)
				inputFile >> c[i][j][k];

	int count = 0;
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= n; ++j)
			nodeTag[i][j] = ++count;

	int source = ++count;
	int destination = ++count;

	int sum = 0;
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= n; ++j) {
			sum += a[i][j] + b[i][j];

			AddDirectedEdge(source, nodeTag[i][j], a[i][j]);
			AddDirectedEdge(nodeTag[i][j], destination, b[i][j]);

			if (i + 1 <= n)
				AddUnDirectedEdge(nodeTag[i][j], nodeTag[i + 1][j], c[i][j][2]);
			if (j + 1 <= n)
				AddUnDirectedEdge(nodeTag[i][j], nodeTag[i][j + 1], c[i][j][1]);
		}
	}

	outputFile << sum - GetMaxFlow(source, destination) << '\n';

	inputFile.close();
	outputFile.close();

	return 0;
}

//Trust me, I'm the Doctor!