Cod sursa(job #2029446)

Utilizator akaprosAna Kapros akapros Data 30 septembrie 2017 10:07:11
Problema Pixels Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.56 kb
#include <bits/stdc++.h>
#define maxN 102
#define maxD 10004
#define mp make_pair
#define pii pair < int, int >
#define fi first
#define sec second
#define inf 1000000000

using namespace std;

FILE *fin = freopen("pixels.in", "r", stdin);
FILE *fout = freopen("pixels.out", "w", stdout);

int n, a[maxN][maxN], b[maxN][maxN], c[maxN][maxN][4];

int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
int Nod[maxN][maxN];
/* ------------- MaxFlow ------------ */
int idx, S, D;
pii deUnde[maxD];
queue < int > Q;
vector < pair < int, int > > G[maxD];
int r[maxD * 8], P[maxD * 8];
int ans;


void BFS(int S, int D)
{
    for (int i = 0; i <= D; ++ i)
        deUnde[i] = mp(-1, -1);

    Q.push(S);
    deUnde[S] = mp(S, 0);
    deUnde[D] = mp(D, 0);
    while (!Q.empty())
    {
        int x = Q.front();
        Q.pop();
        for (pii i : G[x])
            if (r[i.sec] > 0 && deUnde[i.fi].fi == -1)
            {
                deUnde[i.fi] = mp(x, i.sec);
                Q.push(i.fi);
            }
    }
}
int maxFlow()
{

    int ret = 0;
    bool continua = true;
    while (continua)
    {
        BFS(S, D);
        continua = false;

        for(pii u : G[D])
            if (r[u.sec] > 0 && deUnde[u.fi].fi != -1 && u.fi != D)
            {
                continua = true;
                deUnde[D] = u;
                int nod = D;
                int cap = inf;
                while (nod != S)
                {
                    cap = min(cap, r[deUnde[nod].sec]);
                    nod = deUnde[nod].fi;
                }
                nod = D;
                ret += cap;
                while (nod != S)
                {
                    r[deUnde[nod].sec] -= cap;
                    r[P[deUnde[nod].sec]] += cap;
                    nod = deUnde[nod].fi;
                }
            }
    }
    return ret;
}
void compNet()
{
    D = n * n + 1;
    for (int i = 1; i <= n; ++ i)
        for (int j = 1; j <= n; ++ j)
        {
            G[Nod[i][j]].push_back(mp(S, ++ idx));
            G[S].push_back(mp(Nod[i][j], ++ idx));
            r[idx] = r[idx - 1] = a[i][j];
            P[idx] = idx - 1;
            P[idx - 1] = idx;
            G[Nod[i][j]].push_back(mp(D, ++ idx));
            G[D].push_back(mp(Nod[i][j], ++ idx));
            r[idx] = r[idx - 1] = b[i][j];
            P[idx] = idx - 1;
            P[idx - 1] = idx;
        }
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; ++ i)
        for (int j = 1; j <= n; ++ j)
            scanf("%d", &a[i][j]);

    for (int i = 1; i <= n; ++ i)
        for (int j = 1; j <= n; ++ j)
        {
            scanf("%d", &b[i][j]);
            ans += a[i][j] + b[i][j];
            Nod[i][j] = ++ idx;
        }
    idx = 0;
    for (int i = 1; i <= n; ++ i)
        for (int j = 1; j <= n; ++ j)
            for (int t = 0; t < 4; ++ t)
            {
                scanf("%d", &c[i][j][t]);
                if (c[i][j][t] && t > 1)
                {
                    //r[mp(Nod[i][j], Nod[i + dx[t]][j + dy[t]])] =
                    //    r[mp(Nod[i + dx[t]][j + dy[t]], Nod[i][j])] = c[i][j][t];
                    G[Nod[i][j]].push_back(mp(Nod[i + dx[t]][j + dy[t]], ++ idx));
                    G[Nod[i + dx[t]][j + dy[t]]].push_back(mp(Nod[i][j], ++ idx));
                    P[idx] = idx - 1;
                    P[idx - 1] = idx;
                    r[idx] = r[idx - 1] = c[i][j][t];
                }
            }

    compNet();
    printf("%d\n", ans - maxFlow());
    return 0;
}