Cod sursa(job #565680)

Utilizator katakunaCazacu Alexandru katakuna Data 28 martie 2011 09:42:09
Problema Pixels Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.79 kb
#include <cstdio>
#include <algorithm>
#include <map>
#include <string.h>
#include <vector>
using namespace std;

#define Nmax 110

int n, S, D, sol, M;
int T[Nmax * Nmax], viz[Nmax * Nmax];
int C[8 * Nmax * Nmax];
vector <int> V[Nmax * Nmax];
map <int, int> Ind[Nmax * Nmax];

int di[4] = {-1, 0, 1, 0};
int dj[4] = {0, 1, 0, -1};

void citire () {

    int i, j, k, cst;

    scanf ("%d", &n);
    S = n * n + 1; D = n * n + 2;
    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++) {
            scanf ("%d", &cst); sol+= cst;
            V[S].push_back (n * i + j);
            Ind[S][n * i + j] = ++M;
            C[M] = cst;
            V[n * i + j].push_back (S);
            Ind[n * i + j][S] = ++M;
            C[M] = cst;
        }

    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++) {
            scanf ("%d", &cst); sol+= cst;

            V[D].push_back (n * i + j);
            Ind[D][n * i + j] = ++M;
            C[M] = cst;
            V[n * i + j].push_back (D);
            Ind[n * i + j][D] = ++M;
            C[M] = cst;
        }

    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++)
            for (k = 0 ; k < 4; k++) {
                scanf ("%d", &cst);
                if (i + di[k] >= 0 && i + di[k] < n && j + dj[k] < n && j + dj[k] >= 0 && cst) {
                    V[n * i + j].push_back (n * (i + di[k]) + j + dj[k]);
                    Ind[n * i + j][n * (i + di[k]) + j + dj[k]] = ++M;
                    C[M] = cst;
                }
            }
}

int bfs () {

    int p, u, nod, ok = 0;
    int Q[Nmax * Nmax];
    vector <int>::iterator it;

    memset (T, -1, sizeof (T));
    memset (viz, 0, sizeof (viz));
    viz[S] = 1;

    for (p = u = 1, Q[p] = S; p <= u; p++) {
        nod = Q[p];
        for (it = V[nod].begin (); it != V[nod].end (); it++) {
            if (!viz[*it] && C[Ind[nod][*it]] != 0) {
                if (*it == D) {ok = 1; continue;}
                viz[*it] = 1;
                T[*it] = nod;
                Q[++u] = *it;
            }
        }
    }

    return ok;
}

void rezolva () {

    int minim, nod;
    vector <int>::iterator it;

    while (bfs ()) {

        for (it = V[D].begin (); it != V[D].end (); it++)
            if (T[*it] >= 0){
                minim = C[ Ind[*it][D] ];
                for (nod = *it; T[nod] != -1; nod = T[nod]) {
                    minim = min (minim, C[Ind[T[nod]][nod]]);
                }

                T[D] = *it;
                for (nod = D; T[nod] != -1; nod = T[nod]) {
                    C[ Ind[T[nod]][nod] ]-= minim;
                    C[ Ind[nod][T[nod]] ]+= minim;
                }

                sol-= minim;
            }
    }


    printf ("%d", sol);
}

int main () {

    freopen ("pixels.in", "r", stdin);
    freopen ("pixels.out", "w", stdout);

    citire ();
    rezolva ();

    return 0;
}