Cod sursa(job #2030661)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 1 octombrie 2017 22:21:10
Problema Pixels Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.62 kb
#include <bits/stdc++.h>
using namespace std;

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

const int DIM = 105;

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

int mat1[DIM][DIM], mat2[DIM][DIM];
int fth[DIM * DIM], whn[DIM][DIM], bke[DIM * DIM];

struct edge {
    int x, y, c;
} edgl[DIM * DIM * 10];

vector<int> edg[DIM * DIM];

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

inline void add(int x, int y, int c, int &cnt)
{
    edg[x].push_back(cnt);
    edgl[cnt++] = {x, y, c};
}

inline int bfs(int src, int dst)
{
    deque<int> que(1, src);
    fill(bke, bke + dst + 1, 0);

    for (; que.size(); que.pop_front()) {
        int cnd = que.front();
        
        if (cnd == dst)
            continue;
        
        for (int it : edg[cnd]) {
            if (edgl[it].c == 0 or bke[edgl[it].y])
                continue;
            
            bke[edgl[it].y] = it;
            que.push_back(edgl[it].y);
        }
    }
    
    return bke[dst];
}

inline int mincut(int src, int dst)
{
    int mxf = 0;
    while (bfs(src, dst)) {
        for (int it: edg[dst]) {
            if (!bke[edgl[it].y] or !edgl[it ^ 1].c)
                continue;
           
            bke[dst] = it ^ 1;
            int aux = numeric_limits<int> :: max();
            for (int x = dst; x != src; x = edgl[bke[x]].x)
                aux = min(aux, edgl[bke[x]].c);
            
            if (!aux)
                continue;
           
            mxf += aux;
            for (int x = dst; x != src; x = edgl[bke[x]].x) {
                edgl[bke[x]].c -= aux;
                edgl[bke[x] ^ 1].c += aux;
            }
        }
    }
    
    return mxf;
}

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, cnt = 2, s = 0;
    for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
        s += mat1[i][j] + mat2[i][j];
        
        add(src, g(i, j, n), mat1[i][j], cnt);
        add(g(i, j, n), src, 0, cnt);
        
        add(g(i, j, n), dst, mat2[i][j], cnt);
        add(dst, g(i, j, n), 0, cnt);
        
        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) {
                add(g(i, j, n), g(ii, jj, n), c, cnt);
                add(g(ii, jj, n), g(i, j, n), c, cnt);
            }
        }
    } }
    
    out << s - mincut(src, dst) << endl;
    return 0;
}