Cod sursa(job #2408506)

Utilizator SqueekDanielTodasca Daniel SqueekDaniel Data 18 aprilie 2019 02:06:11
Problema Pixels Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.14 kb
#include <bits/stdc++.h>

class EdmondKarp {
public:
    EdmondKarp() {}
    EdmondKarp(std::vector <std::vector <int>>& graph, std::vector <std::vector <int>>& cap, int S, int T) : S(S), T(T), flowValue(0) {
        flow.resize(graph.size(), std::vector <int> (graph.size(), 0));
        parent.resize(graph.size(), 0);
        seen.resize(graph.size(), 0);
        this->graph = &graph;
        this->cap = &cap;

        while (BFS()) {
            for (auto adj:graph[T]) if (seen[adj] && flow[adj][T] != cap[adj][T]) {
                parent[T] = adj;
                int min = cap[adj][T] - flow[adj][T];
                int x = T;
                while (x != S)
                    min = std::min(min, cap[parent[x]][x] - flow[parent[x]][x]), x = parent[x];
                if (min == 0) continue;
                x = T;
                while (x != S)
                    flow[parent[x]][x] += min, flow[x][parent[x]] -= min, x = parent[x];
                flowValue += min;
            }
        }
    }

    inline int getMaxFlow() {return flowValue;}
    std::vector <int>& operator [] (int idx) {return flow[idx];}

private:
    int S, T, flowValue;
    std::queue <int> queue;
    std::vector <int> parent; std::vector <bool> seen;
    std::vector <std::vector <int>> flow, *graph, *cap;
    bool BFS() {
        for (int i=0; i<graph->size(); ++i)
            seen[i] = 0;
        queue.push(S), seen[S] = 0;
        int front;
        while (!queue.empty()) {
            front = queue.front();
            queue.pop();
            if (front == T) continue;
            for (auto adj:((*graph)[front]))
                if (!seen[adj] && flow[front][adj] != (*cap)[front][adj])
                    queue.push(adj), seen[adj] = 1, parent[adj] = front;
        }   return seen[T];
    }
};

#define NETWORK_SIZE N*N+2*N+2

int N, sum;
std::vector <std::vector <int>> graph, cap;

inline void addEdge(int x, int y, int c0, int c1 = 0) {
    graph[x].push_back(y);
    cap[x][y] = c0;
    graph[y].push_back(x);
    cap[y][x] = c1;
}

inline int hash(int x, int y) {return (x-1)*N + y;}

std::ifstream input ("pixels.in");
std::ofstream output("pixels.out");

void readInput() {
    input >> N;
    graph.resize(NETWORK_SIZE);
    cap.resize(NETWORK_SIZE, std::vector <int> (NETWORK_SIZE, 0));

    for (int i=1, j, x; i<=N; ++i)
        for (j=1; j<=N; ++j)
            input >> x, sum += x,
            addEdge(0, hash(i, j), x);

    for (int i=1, j, x; i<=N; ++i)
        for (j=1; j<=N; ++j)
            input >> x, sum += x,
            addEdge(hash(i, j), N*N+1, x);

    int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, 1, -1};
    for (int i=1, j, x, k, X, Y; i<=N; ++i)
        for (j=1; j<=N; ++j)
            for (k=0; k<4; ++k) {
                input >> x;
                X = i + dx[k], Y = j + dy[k];
                if (X < 1 || Y < 1 || X > N || Y > N) continue;
                addEdge(hash(i, j), hash(X, Y), x, x);
            }
}

void solveInput() {
    output << sum - (EdmondKarp(graph, cap, 0, N*N+1)).getMaxFlow();
}

int main()
{
    readInput();
    solveInput();

    return 0;
}