Cod sursa(job #1557177)

Utilizator tamionvTamio Vesa Nakajima tamionv Data 26 decembrie 2015 21:59:39
Problema Pixels Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.67 kb
#include <fstream>
#include <iostream>
#include <array>
#include <vector>
#include <queue>
#include <list>
using namespace std;

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

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

int max_flux(vector<list<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<list<muchie>>& graf;
public:
	graf_builder(vector<list<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].push_back((muchie){ a, 0, 0});
		graf[a].back().opus = &(graf[b].back());
		graf[b].back().opus = &(graf[a].back()); } };

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

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

	g << rez;

	return 0; }