Cod sursa(job #987421)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 20 august 2013 17:46:15
Problema Pixels Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.44 kb
#include <cstdio>
#include <cassert>

#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

const int MAX_D = 4;
const int DX[] = {-1, 0, 1, 0};
const int DY[] = {0, 1, 0, -1};

class Edge {
  public:
    int u, v, capacity, flow;

    Edge() {}

    Edge(const int u, const int v, const int capacity) {
        this->u = u;
        this->v = v;
        this->capacity = capacity;
        this->flow = 0;
    }

    bool Saturated() const {
        return capacity == flow;
    }
};

class Graph {
  public:
    static const int NIL = -1;
    static const int oo = 0x3f3f3f3f;

    int V, E;
    vector< vector<int> > G;
    vector<Edge> edges;

    Graph(const int V = 0) {
        this->V = V;
        this->E = 0;
        this->G = vector< vector<int> >(V, vector<int>());
        this->edges = vector<Edge>();
    }

    void AddEdge(const Edge &edge) {
        edges.push_back(edge);
        G[edge.u].push_back(E);
        ++E;
    }

    int MaxFlow(const int source, const int sink) {
        InitializeFlowNetwork();
        vector<int> father = vector<int>(V, NIL);
        int maxFlow = 0;
        while (BFS(source, sink, father)) {
            for (const auto &e: G[sink]) {
                if (edges[NonEdge(e)].Saturated() || father[edges[e].v] == NIL)
                    continue;
                father[sink] = NonEdge(e);
                int flow = oo;
                for (int x = sink; x != source; x = edges[father[x]].u)
                    flow = min(flow, edges[father[x]].capacity - edges[father[x]].flow);
                for (int x = sink; x != source; x = edges[father[x]].u) {
                    edges[father[x]].flow += flow;
                    edges[NonEdge(father[x])].flow -= flow;
                }
                maxFlow += flow;
            }
        }
        ClearResidualNetwork();
        return maxFlow;
    }

  private:
    int NonEdge(const int edgeIndex) const {
        if (edgeIndex < E)
            return edgeIndex + E;
        return edgeIndex - E;
    }

    bool BFS(const int start, const int end, vector<int> &father) {
        for (auto &f: father)
            f = NIL;
        father[start] = start;
        queue<int> q;
        for (q.push(start); !q.empty(); q.pop()) {
            int x = q.front();
            if (x == end)
                continue;
            for (const auto &e: G[x]) {
                if (!edges[e].Saturated() && father[edges[e].v] == NIL) {
                    father[edges[e].v] = e;
                    q.push(edges[e].v);
                }
            }
        }
        return father[end] != NIL;
    }

    void InitializeFlowNetwork() {
        edges.resize(2 * E);
        for (int e = 0; e < E; ++e) {
            edges[e].flow = 0;
            edges[NonEdge(e)] = Edge(edges[e].v, edges[e].u, 0);
            G[edges[e].v].push_back(NonEdge(e));
        }
    }

    void ClearResidualNetwork() {
        edges.resize(E);
        for (int e = E - 1; e >= 0; --e)
            G[edges[e].v].pop_back();
    }
};

Graph G;
int N, Solution;

inline int Vertex(const int x, const int y) {
    return x * N + y;
}

void Solve() {
    Solution -= G.MaxFlow(N * N, N * N + 1);
}

void Read() {
    assert(freopen("pixels.in", "r", stdin));
    assert(scanf("%d", &N) == 1);
    G = Graph(N * N + 2);
    for (int x = 0; x < N; ++x) {
        for (int y = 0; y < N; ++y) {
            int cost;
            assert(scanf("%d", &cost) == 1);
            G.AddEdge(Edge(N * N, Vertex(x, y), cost));
            Solution += cost;
        }
    }
    for (int x = 0; x < N; ++x) {
        for (int y = 0; y < N; ++y) {
            int cost;
            assert(scanf("%d", &cost) == 1);
            G.AddEdge(Edge(Vertex(x, y), N * N + 1, cost));
            Solution += cost;
        }
    }
    for (int x = 0; x < N; ++x) {
        for (int y = 0; y < N; ++y) {
            for (int d = 0; d < MAX_D; ++d) {
                int cost;
                assert(scanf("%d", &cost) == 1);
                int nx = x + DX[d], ny = y + DY[d];
                if (0 <= nx && nx < N && 0 <= ny && ny < N)
                    G.AddEdge(Edge(Vertex(x, y), Vertex(nx, ny), cost));
            }
        }
    }
}

void Print() {
    assert(freopen("pixels.out", "w", stdout));
    printf("%d\n", Solution);
}

int main() {
    Read();
    Solve();
    Print();
    return 0;
}