Pagini recente » Cod sursa (job #2641359) | Cod sursa (job #695525) | Cod sursa (job #1013551) | Cod sursa (job #3277018) | Cod sursa (job #1557177)
#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; }