Cod sursa(job #1874049)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 9 februarie 2017 17:29:04
Problema Pixels Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.11 kb
#include <bits/stdc++.h>

using namespace std;

class InputReader {
public:
    InputReader() {}
    InputReader(const char *file_name) {
        input_file = fopen(file_name, "r");
        cursor = 0;
        fread(buffer, SIZE, 1, input_file);
    }
    inline InputReader &operator >>(int &n) {
        while(buffer[cursor] < '0' || buffer[cursor] > '9') {
            advance();
        }
        n = 0;
        while('0' <= buffer[cursor] && buffer[cursor] <= '9') {
            n = n * 10 + buffer[cursor] - '0';
            advance();
        }
        return *this;
    }
private:
    FILE *input_file;
    static const int SIZE = 1 << 17;
    int cursor;
    char buffer[SIZE];
    inline void advance() {
        ++ cursor;
        if(cursor == SIZE) {
            cursor = 0;
            fread(buffer, SIZE, 1, input_file);
        }
    }
};

//MaxFlow
int n, m, s, t;

const int NMAX = 100 + 5;
int from[12 * NMAX * NMAX], to[12 * NMAX * NMAX];
int cap[12 * NMAX * NMAX];

inline int other(int edge, int node) {
    return from[edge] ^ to[edge] ^ node;
}

vector <int> graph[NMAX * NMAX];

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

void addEdge(int frm, int _to, int cp) {
    from[m] = frm;
    to[m] = _to;
    cap[m ++] = cp;
    from[m] = _to;
    to[m ++] = frm;

    graph[frm].push_back(m - 2);
    graph[_to].push_back(m - 1);
}

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();

        if (node == t)
            return true;

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

    return vis[t];
}

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

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

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

                while (node != s) {
                    cap[father[node]] -= minimum;
                    cap[father[node] ^ 1] += minimum;
                    node = other(father[node], node);
                }
            }
    }

    return flow;
}

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

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

int main()
{
    InputReader 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;

    s = ++ sz;
    t = ++ sz;
    n = 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];

            addEdge(s, label[i][j], b[i][j]);
            addEdge(label[i][j], t, a[i][j]);

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

    cout << sum - Dinic() << '\n';
    return 0;
}