Cod sursa(job #2200392)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 1 mai 2018 11:13:26
Problema Pixels Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.81 kb
#include <bits/stdc++.h>

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

const int DIM = 105;

template <class CapacityType>
class MaxFlow {
private:
    static constexpr int NIL = -1;
    static constexpr long double EPS = 1e-6;
    
    static constexpr CapacityType INF =
    std::numeric_limits<CapacityType> :: max() / 2;
    
    template <class type>
    int cmp(type x) {
        if (-EPS < x and x < EPS)
            return 0;
        return x < 0 ? -1 : 1;
    }
    
    struct Edge {
        int nod, nxt;
        CapacityType cap;
        
        Edge() :
            nod(0), nxt(0), cap(0) {};
        Edge(int _nod, int _nxt, CapacityType _cap) :
            nod(_nod), nxt(_nxt), cap(_cap) {};
    }; std::vector<Edge> lst;
    
    std::vector<bool> oki; int ptr = 0;
    std::vector<int> beg, que, adj, dis;
    
    bool bfs(const int src, const int dst) {
        std::fill(dis.begin(), dis.end(), (CapacityType)INF);
        dis[src] = 0; que[0] = src;
        
        for (int qbg = 0, qen = 0; qbg <= qen; ++qbg) {
            const int x = que[qbg];
            
            for (int it = beg[x]; it != NIL; it = lst[it].nxt) {
                const int y = lst[it].nod;
                
                if (cmp(lst[it].cap) > 0 and dis[y] == INF)
                    dis[y] = dis[x] + 1, que[++qen] = y;
            }
        }
        
        return dis[dst] != INF;
    }
    
    CapacityType dfs(const int x, const int dst, const CapacityType cap) {
        if (!cmp(cap) or x == dst)
            return cap;
        
        for (; adj[x] != NIL; adj[x] = lst[adj[x]].nxt) {
            const int y = lst[adj[x]].nod;
            
            if (cmp(lst[adj[x]].cap) > 0 and dis[y] == dis[x] + 1) {
                const CapacityType aux = dfs(y, dst, std::min(cap, lst[adj[x]].cap));
                
                if (cmp(aux)) {
                    lst[adj[x]].cap -= aux;
                    lst[adj[x] ^ 1].cap += aux;
                    return aux;
                }
            }
        }
        
        return 0;
    }
    
    void fill(const int x) {
        oki[x] = true;
        
        for (int it = beg[x]; it != NIL; it = lst[it].nxt) {
            const int y = lst[it].nod;
            
            if (cmp(lst[it].cap) > 0 and !oki[y])
                fill(y);
        }
    }
public:
    MaxFlow(int szn, int szm) {
        dis.resize(szn); beg.resize(szn);
        que.resize(szn); adj.resize(szn);
        oki.resize(szn); lst.resize(szm); // m != n
        
        std::fill(beg.begin(), beg.end(), (int)NIL);
    }
    
    inline void addDirectedEdge(const int x, const int y, const CapacityType cap) {
        lst[ptr] = Edge(y, beg[x], cap); beg[x] = ptr++;
        lst[ptr] = Edge(x, beg[y],  0 ); beg[y] = ptr++;
    }
    
    inline void addUndirectedEdge(const int x, const int y, const CapacityType cap) {
        lst[ptr] = Edge(y, beg[x], cap); beg[x] = ptr++;
        lst[ptr] = Edge(x, beg[y], cap); beg[y] = ptr++;
    }
    
    CapacityType getMaxFlow(const int src, const int dst) {
        CapacityType aux, ans = 0;
        
        while (bfs(src, dst)) {
            copy(beg.begin(), beg.end(), adj.begin());
            
            do {
                aux = dfs(src, dst, INF);
                ans += aux;
            } while (cmp(aux));
        }
        
        return ans;
    }
    
    CapacityType getMinCut(const int src, const int dst, std::vector<int> &ans) {
        std::fill(oki.begin(), oki.end(), false);
        CapacityType sol = getMaxFlow(src, dst); fill(src);
        
        ans.clear();
        for (int i = 0; i < oki.size(); ++i)
            if (oki[i]) ans.push_back(i);
        
        return sol;
    }
};MaxFlow<int> myNetwork(DIM * DIM + 5, DIM * DIM * 11);

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