Cod sursa(job #1873805)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 9 februarie 2017 13:57:22
Problema Pixels Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.44 kb
#include <bits/stdc++.h>

using namespace std;

template <const int NMAX, const int MMAX>
class MaxFLow {
public:
    MaxFLow() { m = 0; }

    inline void setN(int _n) { n = _n; }
    inline void setS(int _s) { s = _s; }
    inline void setT(int _t) { t = _t; }

    inline int getN() { return n; }
    inline int getS() { return s; }
    inline int getT() { return t; }

    void clear() {
        m = 0;
        for (int i = 1; i <= n; ++ i)
            graph[i].clear();
    }

    void reset() {
        for (int i = 0; i < m; ++ i)
            edges[i].flow = 0;
    }

    void addEdge(int from, int to, int cap) {
        edges[m ++] = Edge(from, to, 0, cap);
        edges[m ++] = Edge(to, from, 0, 0);

        graph[from].push_back(m - 2);
        graph[to].push_back(m - 1);
    }

    inline int computeFlow() {
        return Dinic();
    }

private:
    struct Edge {
        int from, to;
        int flow, cap;

        Edge(int _from = 0, int _to = 0, int _flow = 0, int _cap = 0):
            from(_from), to(_to), flow(_flow), cap(_cap) {}
        inline int other(int node) {
            return from ^ to ^ node;
        }
    };

    int n, m, s, t;

    vector <int> graph[NMAX];
    Edge edges[2 * MMAX];

    int father[NMAX];
    bool vis[NMAX];
    queue <int> _queue;

    bool bfs() {
        memset(vis, 0, (n + 1) * sizeof(bool));

        vis[s] = true;
        _queue.push(s);

        int node;
        while (!_queue.empty()) {
            node = _queue.front();
            _queue.pop();

            for (auto it: graph[node])
                if (!vis[edges[it].other(node)] && edges[it].flow < edges[it].cap) {
                    father[edges[it].other(node)] = it;
                    vis[edges[it].other(node)] = true;
                    _queue.push(edges[it].other(node));
                }
        }

        return vis[t];
    }

    int Dinic() {
        int flow = 0;
        while (bfs()) {
            for (auto it: graph[t])
                if (vis[edges[it ^ 1].other(t)] && edges[it ^ 1].flow < edges[it ^ 1].cap) {
                    int node = edges[it ^ 1].other(t);
                    int minimum = edges[it ^ 1].cap - edges[it ^ 1].flow;

                    while (node != s) {
                        minimum = min(minimum, edges[father[node]].cap - edges[father[node]].flow);
                        node = edges[father[node]].other(node);
                    }

                    node = edges[it ^ 1].other(t);
                    edges[it ^ 1].flow += minimum;
                    edges[it].flow -= minimum;
                    flow += minimum;

                    while (node != s) {
                        edges[father[node]].flow += minimum;
                        edges[father[node] ^ 1].flow -= minimum;

                        node = edges[father[node]].other(node);
                    }
                }
        }

        return flow;
    }
};

const int NMAX = 100 + 5;

MaxFLow <NMAX * NMAX, 5 * NMAX * NMAX> f;

int N;
int a[NMAX][NMAX];
int b[NMAX][NMAX];
int c[NMAX][NMAX][4];

int sz;
int label[NMAX][NMAX];

int main()
{
    ifstream cin("pixels.in");
    ofstream cout("pixels.out");

    cin >> N;
    for (int i = 1; i <= N; ++ i)
        for (int j = 1; j <= N; ++ j)
            cin >> a[i][j];
    for (int i = 1; i <= N; ++ i)
        for (int j = 1; j <= N; ++ j)
            cin >> b[i][j];

    for (int i = 1; i <= N; ++ i)
        for (int j = 1; j <= N; ++ j)
            for (int k = 0; k < 4; ++ k)
                cin >> c[i][j][k];

    for (int i = 1; i <= N; ++ i)
        for (int j = 1; j <= N; ++ j)
            label[i][j] = ++ sz;

    f.setS(++ sz);
    f.setT(++ sz);
    f.setN(sz);

    int sum = 0;
    for (int i = 1; i <= N; ++ i)
        for (int j = 1; j <= N; ++ j) {
            sum += a[i][j] + b[i][j];

            f.addEdge(f.getS(), label[i][j], b[i][j]);
            f.addEdge(label[i][j], f.getT(), a[i][j]);

            if (j + 1 <= N) {
                f.addEdge(label[i][j], label[i][j + 1], c[i][j][1]);
                f.addEdge(label[i][j + 1], label[i][j], c[i][j][1]);
            }
            if (i + 1 <= N) {
                f.addEdge(label[i][j], label[i + 1][j], c[i][j][2]);
                f.addEdge(label[i + 1][j], label[i][j], c[i][j][2]);
            }
        }

    cout << sum - f.computeFlow() << '\n';
    return 0;
}