Cod sursa(job #1557179)

Utilizator tamionvTamio Vesa Nakajima tamionv Data 26 decembrie 2015 22:04:38
Problema Pixels Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.75 kb
#include <fstream>
#include <iostream>
#include <array>
#include <vector>
#include <queue>
using namespace std;

struct muchie{
	int dest, flux, cap, ind_opus;
	muchie *opus; };

int augmentable(const muchie& m){
	return m.cap - m.flux; }

int max_flux(vector<vector<muchie>>& graf, const int surs, const int dest){

	const int n = graf.size();
	vector<muchie*> tata(n, nullptr);
	queue<int> de_viz;
	int rez = 0;
	while(true){
		de_viz.push(surs);
		while(!de_viz.empty()){
			const int cur = de_viz.front();	
			de_viz.pop();
			for(auto& next : graf[cur]){
				if(augmentable(next) && tata[next.dest] == nullptr){
					tata[next.dest] = &next;
					if(next.dest != dest){
						de_viz.push(next.dest); } } } }
		if(tata[dest] == nullptr){
			return rez; }
		for(const auto& vec_muc : graf[dest]){
			const auto vec = vec_muc.dest;
			if(tata[vec] != nullptr && augmentable(*vec_muc.opus)){
				int delta = 1000000000;
				tata[dest] = vec_muc.opus;
				for(int cur = dest; cur != surs; cur = tata[cur]->opus->dest){
					delta = min(delta, augmentable(*tata[cur])); }
				for(int cur = dest; cur != surs; cur = tata[cur]->opus->dest){
					tata[cur]->flux += delta;
					tata[cur]->opus->flux -= delta; }
				rez += delta; } }
		fill(begin(tata), end(tata), nullptr); } }

class graf_builder{
	vector<vector<muchie>>& graf;
public:
	graf_builder(vector<vector<muchie>>& to_build, const int n): graf(to_build){
		graf.resize(n); }
	void operator()(const int a, const int b, const int cap){
		graf[a].push_back((muchie){ b, 0, cap, graf[b].size()});
		graf[b].push_back((muchie){ a, 0, 0, graf[a].size()-1}); }
	void knit(){
		for(auto& x : graf){
			for(auto& y : x){
				y.opus = &(graf[y.dest][y.ind_opus]); } } } };

class codificare_graf_matrice{
	int n;
public:
	codificare_graf_matrice(const int N): n(N){}
	int operator()(const int a, const int b){
		return 2 + a * n + b; }
	int surs(){
		return 0; }
	int dest(){
		return 1; }
	int size(){
		return 2 + n * n; } };

constexpr array<int, 4> dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};

int main(){
	ifstream f("pixels.in");
	ofstream g("pixels.out");

	int n;
	f >> n;
	codificare_graf_matrice encode(n);

	vector<vector<muchie>> graf;
	graf_builder add_muc(graf, encode.size());

	int rez = 0;

	for(int i = 0, x; i < n; ++i){
		for(int j = 0; j < n; ++j){
			f >> x;
			rez += x;
			add_muc(encode.surs(), encode(i, j), x); } }

	for(int i = 0, x; i < n; ++i){
		for(int j = 0; j < n; ++j){
			f >> x;
			rez += x;
			add_muc(encode(i, j), encode.dest(), x); } }

	for(int i = 0, x; i < n; ++i){
		for(int j = 0; j < n; ++j){
			for(int d = 0; d < 4; ++d){
				f >> x;
				if(x != 0){
					add_muc(encode(i, j), encode(i + dx[d], j + dy[d]), x); } } } }

	add_muc.knit();
	
	rez -= max_flux(graf, encode.surs(), encode.dest());

	g << rez;

	return 0; }