Cod sursa(job #2134640)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 18 februarie 2018 10:38:50
Problema Pixels Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.65 kb
#include <bits/stdc++.h>

std::ifstream in("pixels.in");
std::ofstream out("pixels.out");

const int DIM = 105;

// unverified
class MaxFlow {
private:
    static constexpr int INF = std::numeric_limits<int> :: max() / 2;
    static constexpr long double EPS = 1e-6;
    /*
    static inline int cmp(const int x) {
        if (fabs(x) < EPS)
            return 0;
        return x < 0 ? -1 : 1;
    }
    */
    struct edge {
        int x, y; int flo, cap;
        
        edge(int _x, int _y, int _cap) :
        x(_x), y(_y), cap(_cap), flo(0) {};
    };
    
    std::vector<edge> lst; std::vector<int> dis; std::vector<int> ptx;
    std::vector<std::vector<int>> edg; std::vector<bool> oki;
    
    bool bfs(const int src, const int dst, int cap) {
        std::fill(dis.begin(), dis.end(), (int)INF); dis[src] = 0;
        
        for (std::deque<int> que(1, src); que.size() and dis[dst] == INF; que.pop_front()) {
            int x = que.front();
            if (x == dst) continue;
            
            for (int it : edg[x]) {
                int y = lst[it].y;
                
                if (lst[it].cap - lst[it].flo - cap < 0)
                    continue;
                if (dis[y] > dis[x] + 1) {
                    dis[y] = dis[x] + 1;
                    que.push_back(y);
                }
            }
        }
        
        return dis[dst] != INF;
    }
    
    bool dfs(const int x, const int dst, int cap) {
        if (x == dst) return cap;
        
        for (; ptx[x] < edg[x].size(); ++ptx[x]) {
            int it = edg[x][ptx[x]], y = lst[it].y;
            
            if (dis[y] - dis[x] - 1 != 0 or
                lst[it].cap - lst[it].flo - cap < 0)
                continue;
            
            if (dfs(y, dst, cap)) {
                lst[it].flo += cap;
                lst[it ^ 1].flo -= cap;
                return true;
            }
        }
        
        return false;
    }
    
    void fill(const int x, std::vector<int> &ans) {
        oki[x] = true;
        
        for (int it : edg[x]) {
            int y = lst[it].y;
            
            if (lst[it].cap - lst[it].flo and !oki[y])
                fill(y, ans);
        }
    }
public:
    MaxFlow(int sz) {
        edg.resize(sz); dis.resize(sz);
        oki.resize(sz); ptx.resize(sz);
    }
    
    void addUndirectedEdge(const int x, const int y, const int c) {
        edg[x].push_back((int) lst.size()); lst.push_back(edge(x, y, c));
        edg[y].push_back((int) lst.size()); lst.push_back(edge(y, x, c));
    }
    
    void addDirectedEdge(const int x, const int y, const int c) {
        edg[x].push_back((int) lst.size()); lst.push_back(edge(x, y, c));
        edg[y].push_back((int) lst.size()); lst.push_back(edge(y, x, 0));
    }
    
    int getMaxFlow(const int src, const int dst) {
        int lim = INF;
        for (int i = 0; i < lst.size(); ++i) {
            lst[i].flo = 0;
            lim = std::max(lim, lst[i].cap);
        }
        
        int ans = 0;
        for (; lim; ) {
            if (!bfs(src, dst, lim)) {
                lim /= 2;
                continue;
            }
            
            std::fill(ptx.begin(), ptx.end(), 0);
            while (dfs(src, dst, lim))
                ans += lim;
        }
        
        return ans;
    }
    
    int getMinCut(const int src, const int dst, std::vector<int> &ans) {
        std::fill(oki.begin(), oki.end(), false);
        int sol = getMaxFlow(src, dst);
        
        fill(src, ans); ans.clear();
        for (int i = 0; i < edg.size(); ++i)
            if (oki[i]) ans.push_back(i);
        
        return sol;
    }
}; MaxFlow myNetwork(DIM * DIM + 2);

const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, 1, 0, -1};

int mat1[DIM][DIM], mat2[DIM][DIM];

inline int g(int x, int y, int n)
{
    return x * n + y;
}

int main(void) {
    int n;
    in >> n;
    
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            in >> mat1[i][j];
    
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            in >> mat2[i][j];
    
    int src = n * n, dst = n * n + 1, s = 0;
    for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
        s += mat1[i][j] + mat2[i][j];
        
        myNetwork.addDirectedEdge(src, g(i, j, n), mat1[i][j]);
        myNetwork.addDirectedEdge(g(i, j, n), dst, mat2[i][j]);
        
        for (int k = 0; k < 4; ++k) {
            int c, ii = i + dx[k], jj = j + dy[k];
            in >> c;
            
            if (k >= 1 and k <= 2 and jj < n and jj < n)
                myNetwork.addUndirectedEdge(g(i, j, n), g(ii, jj, n), c);
        }
    } }
    
    out << s - myNetwork.getMaxFlow(src, dst) << std::endl;
    return 0;
}