Cod sursa(job #1759815)

Utilizator fanache99Constantin-Buliga Stefan fanache99 Data 19 septembrie 2016 21:25:11
Problema Pixels Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.88 kb
#include <fstream>
#include <queue>
#include <cstring>
#include <set>

using namespace std;

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

const int MAXN = 100;
const int INF = 1000000000;

int code[1 + MAXN][1 + MAXN];
int source, sink;
int line[] = {-1, 0, 1, 0};
int column[] = {0, 1, 0, -1}, edges = 0;
vector<int> g[1 + MAXN * MAXN + 1];
int where[1 + 8 * MAXN * MAXN], capacity[1 + 8 * MAXN * MAXN];
int dad[1 + MAXN + 1];

void AddEdge(int from, int to, int value, int inverted) {
    edges++;
    where[edges] = to;
    capacity[edges] = value;
    g[from].push_back(edges);
    edges++;
    where[edges] = from;
    capacity[edges] = inverted;
    g[to].push_back(edges);
}

int f(int x) {
    if (x & 1)
        return x + 1;
    return x - 1;
}

bool BFS() {
    queue<int> Queue;
    memset(dad, -1, sizeof(dad));
    Queue.push(source);
    dad[source] = 0;
    while (!Queue.empty()) {
        int node = Queue.front();
        Queue.pop();
        for (auto &son : g[node])
            if (dad[where[son]] == -1 && capacity[son] > 0) {
                dad[where[son]] = son;
                Queue.push(where[son]);
                if (where[son] == sink)
                    return true;
            }
    }
    return false;
}

int MaximumFlow() {
    int answer = 0;
    while (BFS())
        for (auto &node : g[sink])
            if (capacity[f(node)] && dad[where[node]] != -1) {
                int add = INF;
                for (int node = sink; node != source; node = where[f(dad[node])])
                    if (capacity[dad[node]] < add)
                        add = capacity[dad[node]];
                answer += add;
                for (int node = sink; node != source; node = where[f(dad[node])]) {
                    capacity[dad[node]] -= add;
                    capacity[f(dad[node])] += add;
                }
            }
    return answer;
}

int main() {
    int n, answer = 0;
    cin >> n;
    source = 0;
    sink = n * n + 1;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            code[i][j] = (i - 1) * n + j;
            int value;
            cin >> value;
            answer += value;
            AddEdge(source, code[i][j], value, 0);
        }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            int value;
            cin >> value;
            answer += value;
            AddEdge(code[i][j], sink, value, 0);
        }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            for (int k = 0; k < 4; k++) {
                int value;
                cin >> value;
                if (code[i][j] < code[i + line[k]][j + column[k]])
                    AddEdge(code[i][j], code[i + line[k]][j + column[k]], value, value);
            }
    cout << answer - MaximumFlow() << "\n";
    return 0;
}