Cod sursa(job #1874031)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 9 februarie 2017 17:04:08
Problema Pixels Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.36 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;

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;
    }
};

const int NMAX = 100 + 5;

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

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

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

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;
}

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;
}