Cod sursa(job #2715695)

Utilizator trifangrobertRobert Trifan trifangrobert Data 4 martie 2021 01:10:53
Problema Pixels Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.33 kb
#include <bits/stdc++.h>

using namespace std;

const int NMAX = 100;
const int INF = (1 << 30);
int N;
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
int source, sink;

bool Inside(int i, int j){
    return 0 <= min(i, j) && max(i, j) < N;
}

int Encode(int i, int j){
    return i * N + j;
}

struct Edge{
    int u, v, flow, cap;
};

vector <Edge> edges;
vector <pair <int, int>> graph[NMAX * NMAX + 10];
int indEdge, nodes;
int level[NMAX * NMAX + 10];
int last[NMAX * NMAX + 10];


void AddEdge(int u, int v, int flow, int cap){
    graph[u].push_back(make_pair(v, indEdge));
    edges.push_back({u, v, flow, cap});
    ++indEdge;
    graph[v].push_back(make_pair(u, indEdge));
    edges.push_back({v, u, 0, 0});
    ++indEdge;
}

bool bfs(){
    for (int i = 0;i <= nodes;++i)
        level[i] = INF;
    level[source] = 0;
    queue <int> q;
    q.push(source);
    while (!q.empty()){
        int node = q.front();
        q.pop();
        if (node == sink)
            continue;
        for (auto& x : graph[node]){
            Edge e = edges[x.second];
            if (e.cap > e.flow && level[x.first] > level[node] + 1){
                level[x.first] = level[node] + 1;
                q.push(x.first);
            }
        }
    }
    return (level[sink] != INF);
}

int dfs(int node, int deltaflow){
    if (node == sink)
        return deltaflow;
    else{
        for (int &p = last[node];p < graph[node].size();++p){
            int nnode = graph[node][p].first;
            int ind = graph[node][p].second;
            int flow = edges[ind].flow;
            int cap = edges[ind].cap;
            if (level[nnode] == level[node] + 1 && flow < cap){
                int currflow = dfs(nnode, min(deltaflow, cap - flow));
                if (currflow > 0){
                    edges[ind].flow += currflow;
                    edges[ind ^ 1].flow -= currflow;
                    return currflow;
                }
            }
        }
        return 0;
    }
}

int Dinic(){
    int maxflow = 0;
    while (bfs()){
        for (int i = 0;i <= nodes;++i)
            last[i] = 0;
        int deltaflow = dfs(source, INF);
        while (deltaflow > 0){
            maxflow += deltaflow;
            deltaflow = dfs(source, INF);
        }
    }
    return maxflow;
}

int main()
{
    ifstream fin("pixels.in");
    ofstream fout("pixels.out");
    fin >> N;
    int sum = 0;
    source = N * N;
    sink = N * N + 1;
    nodes = sink;
    for (int i = 0;i < N;++i){
        for (int j = 0;j < N;++j){
            int w;
            fin >> w;
            AddEdge(source, Encode(i, j), 0, w);
            sum += w;
        }
    }
    for (int i = 0;i < N;++i){
        for (int j = 0;j < N;++j){
            int b;
            fin >> b;
            AddEdge(Encode(i, j), sink, 0, b);
            sum += b;
        }
    }
    for (int i = 0;i < N;++i){
        for (int j = 0;j < N;++j){
            int c;
            fin >> c;
            for (int k = 0;k < 4;++k){
                if (2 <= k && k <= 3 && Inside(i + dx[k], j + dy[k])){
                    AddEdge(Encode(i, j), Encode(i + dx[k], j + dy[k]), 0, c);
                }
            }
        }
    }
    fout << sum - Dinic() << "\n";
    fin.close();
    fout.close();
    return 0;
}