Cod sursa(job #2029441)

Utilizator akaprosAna Kapros akapros Data 30 septembrie 2017 09:40:27
Problema Pixels Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.08 kb
#include <bits/stdc++.h>
#define maxN 102
#define maxD 10002
#define mp make_pair
#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 idx, Nod[maxN][maxN];
/* ------------- MaxFlow ------------ */
int S, D, deUnde[maxD];
queue < int > Q;
vector < int > G[maxD];
map < pair < int, int >, int > r;
int ans;


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

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

        for(int u : G[D])
            if (r[mp(u, D)] > 0 && deUnde[u] != -1 && u != D)
            {
                continua = true;
                deUnde[D] = u;
                int nod = D;
                int cap = inf;
                while (nod != S)
                {
                    cap = min(cap, r[mp(deUnde[nod], nod)]);
                    nod = deUnde[nod];
                }
                nod = D;
                ret += cap;
                while (nod != S)
                {
                    r[mp(deUnde[nod], nod)] -= cap;
                    r[mp(nod, deUnde[nod])] += cap;
                    nod = deUnde[nod];
                }
            }
    }
    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(S);
            G[S].push_back(Nod[i][j]);
            r[mp(S, Nod[i][j])] = a[i][j];
            G[Nod[i][j]].push_back(D);
            G[D].push_back(Nod[i][j]);
            r[mp(Nod[i][j], D)] = b[i][j];
        }
}
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;
        }
    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(Nod[i + dx[t]][j + dy[t]]);
                    G[Nod[i + dx[t]][j + dy[t]]].push_back(Nod[i][j]);
                }
            }
    compNet();
    printf("%d\n", ans - maxFlow());
    return 0;
}