Cod sursa(job #2134586)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 18 februarie 2018 09:40:11
Problema Pixels Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.49 kb
#include <bits/stdc++.h>

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

const int DIM = 101;

// unverified
template <class type>
class MaxFlow {
private:
    static constexpr type INF = std::numeric_limits<type> :: max() / 2;
    static constexpr long double EPS = 1e-6;
    
    static inline int cmp(const type x) {
        if (fabs(x) < EPS)
            return 0;
        return x < 0 ? -1 : 1;
    }
    
    struct edge {
        int x, y; type flo, cap;
        
        edge(int _x, int _y, type _cap) :
        x(_x), y(_y), cap(_cap), flo(0) {};
    };
    
    std::vector<edge> lst; std::vector<type> dis;
    std::vector<std::vector<int>> edg; std::vector<bool> oki;
    
    void bfs(const int src, const int dst) {
        std::fill(dis.begin(), dis.end(), (type)INF); dis[src] = 0;
        
        for (std::deque<int> que(1, src); que.size(); que.pop_front()) {
            int x = que.front();
            if (x == dst) continue;
            
            for (int it : edg[x]) {
                int y = lst[it].y;
                
                if (!cmp(lst[it].cap - lst[it].flo))
                    continue;
                if (dis[y] > dis[x] + 1) {
                    dis[y] = dis[x] + 1;
                    que.push_back(y);
                }
            }
        }
    }
    
    type dfs(const int x, const int dst, type cap) {
        if (!cmp(cap)) return 0;
        if (x == dst) return cap;
        
        type flo = 0;
        for (int it : edg[x]) {
            int y = lst[it].y;
            
            if (!cmp(cap - flo))
                break;
            if (!cmp(lst[it].cap - lst[it].flo) or cmp(dis[y] - dis[x] - 1))
                continue;
            type aux = dfs(y, dst, std::min(cap - flo, lst[it].cap - lst[it].flo));
            
            if (cmp(aux) > 0) {
                lst[it].flo += aux;
                lst[it ^ 1].flo -= aux;
                flo += aux;
            }
        }
        
        return flo;
    }
    
    void fill(const int x, std::vector<int> &ans) {
        oki[x] = true;
        
        for (int it : edg[x]) {
            int y = lst[it].y;
            
            if (cmp(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);
    }
    
    void addUndirectedEdge(const int x, const int y, const type 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 type 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));
    }
    
    type getMaxFlow(const int src, const int dst) {
        for (int i = 0; i < lst.size(); ++i)
            lst[i].flo = 0;
        
        type aux, ans = 0;
        do {
            bfs(src, dst);
            aux = dfs(src, dst, INF); ans += aux;
        } while (cmp(aux));
        
        return ans;
    }
    
    type getMinCut(const int src, const int dst, std::vector<int> &ans) {
        fill(oki.begin(), oki.end(), false);
        type 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<int> 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;
}