Cod sursa(job #1772618)

Utilizator bciobanuBogdan Ciobanu bciobanu Data 6 octombrie 2016 21:36:19
Problema Pixels Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.08 kb
/*
 * max(sum(cost_alb) + sum(cost_negru) - sum(cost_culori_distincte_adj))
 * <=> min(sum(cost_culori_distincte_adj)) => taietura minima : sursa = culoarea alb, destinatie = culoarea negru
 */
#include <fstream>
#include <cstring>

using namespace std;

const int kMaxN = 100;
const int kSource = kMaxN * kMaxN;
const int kSink = kMaxN * kMaxN + 1;
const int NIL = -1;

struct Edge {
	int v;
	int cap;
	int next;
} G[kMaxN * kMaxN * 8];

int head[kMaxN * kMaxN + 2];

int dist[kMaxN * kMaxN + 2];
int m_queue[kMaxN * kMaxN + 2];
int dinic_adj[kMaxN * kMaxN + 2];

bool breadth_first() {
	int q_start = 0, q_end = 1;
	
	m_queue[0] = kSource;
	memset(dist, 0, 4 * (kMaxN * kMaxN + 2));
	
	dist[kSource] = 1;

	while (q_start != q_end) {
		const int node = m_queue[q_start++];
		for (int i = head[node]; i != NIL; i = G[i].next) {
			const int adj_node = G[i].v;
			if (G[i].cap > 0 and dist[adj_node] == 0) {
				dist[adj_node] = dist[node] + 1;
				m_queue[q_end++] = adj_node;
			}
		}	
	}
	return dist[kSink] != 0;
}

int df(const int node, const int f_min) {
	if (node == kSink or f_min == 0) {
		return f_min;
	}
	for (; dinic_adj[node] != NIL; dinic_adj[node] = G[dinic_adj[node]].next) {
		
		const int adj_node = G[dinic_adj[node]].v;
		
		if (dist[adj_node] == dist[node] + 1 
				and G[dinic_adj[node]].cap > 0) {
			
			const int push_flow = (f_min < G[dinic_adj[node]].cap 
										? f_min : G[dinic_adj[node]].cap);

			const int pushed = df(adj_node, push_flow);
			
			if (pushed > 0) {
				G[dinic_adj[node]].cap -= pushed;
				G[dinic_adj[node] ^ 1].cap += pushed;
				return pushed;
			}
		}
	}
	return 0;
}

void add_edge(const int u, const int v,
			  const int cap) {
	static int ptr = 0;
	G[ptr].v = v;
	G[ptr].cap = cap;
	G[ptr].next = head[u];
	head[u] = ptr++;
}

int main() {
	ifstream cin("pixels.in");
	ofstream cout("pixels.out");
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	
	int n; cin >> n;
	
	memset(head, NIL, 4 * (kMaxN * kMaxN + 2));
	
	int total_profit = 0;
	for (int i = 0; i < n; i += 1) {
		for (int j = 0; j < n; j += 1) {
			int white_profit; cin >> white_profit;
			add_edge(kSource, i * n + j, white_profit);
			add_edge(i * n + j, kSource, 0);
			total_profit += white_profit;
		}
	}

	for (int i = 0; i < n; i += 1) {
		for (int j = 0; j < n; j += 1) {
			int black_profit; cin >> black_profit;
			add_edge(i * n + j, kSink, black_profit);
			add_edge(kSink, i * n + j, 0);
			total_profit += black_profit;
		}
	}

	for (int i = 0; i < n; i += 1) {
		for (int j = 0; j < n; j += 1) {
			int dir_cost[4];
			for (int k = 0; k < 4; k += 1) {
				cin >> dir_cost[k];
			}
			if (i != 0) {
				add_edge(i * n + j, (i - 1) * n + j, dir_cost[0]);
				add_edge((i - 1) * n + j, i * n + j, dir_cost[0]);
			}
			if (j != 0) {
				add_edge(i * n + j, i * n + j - 1, dir_cost[3]);
				add_edge(i * n + j - 1, i * n + j, dir_cost[3]);
			}
		}
	}
	
	int flow = 0;
	while (breadth_first() == true) {
		int pushed = 0;
		memcpy(dinic_adj, head, 4 * (kMaxN * kMaxN + 2));
		do {
			pushed = df(kSource, 0x3f3f3f3f);
			flow += pushed;
		} while (pushed > 0);
	}

	cout << total_profit - flow << '\n';

	return 0;
}