Cod sursa(job #565686)

Utilizator katakunaCazacu Alexandru katakuna Data 28 martie 2011 10:07:52
Problema Pixels Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.77 kb
#include <cstdio>
#include <algorithm>
#include <string.h>
#include <vector>
using namespace std;

#define Nmax 110

int n, S, D, sol;
int T[Nmax * Nmax];
bool viz[Nmax * Nmax];
vector <int> V[Nmax * Nmax], C[Nmax * Nmax];

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

void citire () {

    int i, j, k, cst, x, y;

    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;
            x = S; y = n * i + j;
            V[x].push_back (y); C[x].push_back (cst);
            V[y].push_back (x); C[y].push_back (cst);
        }

    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++) {
            scanf ("%d", &cst); sol+= cst;
            x = D; y = n * i + j;
            V[x].push_back (y); C[x].push_back (cst);
            V[y].push_back (x); C[y].push_back (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) {
                    x = n * i + j; y = n * (i + di[k]) + j + dj[k];
                    V[x].push_back (y); C[x].push_back (cst);
                }
            }
}

int bfs () {

    int p, u, nod, ok = 0, N, fiu;
    int Q[Nmax * Nmax];
    int i;

    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];
        N = V[nod].size ();
        for (i = 0; i < N; i++) {
            fiu = V[nod][i];
            if (!viz[fiu] && C[nod][i] > 0) {
                if (fiu == D) {ok = 1; continue;}
                viz[fiu] = 1;
                T[fiu] = nod;
                Q[++u] = fiu;
            }
        }
    }

    return ok;
}

inline short ind (const int &x, const int &y) {

    if (x == S || x == D) return y ;

    for (int i = 0; i < V[x].size (); i++)
        if (V[x][i] == y)
            return i;

    return 0;
}

void rezolva () {

    int minim, nod, fr, nn = n * n;
    vector <int>::iterator it;

    while (bfs ())
        for (fr = 0; fr < nn; fr++) {
            if (T[fr] >= 0){
                minim = C[fr][ind(fr, D)];
                for (nod = fr; T[nod] != -1; nod = T[nod])
                    minim = min (minim, C[T[nod]][ind(T[nod], nod)]);

                T[D] = fr;
                for (nod = D; T[nod] != -1; nod = T[nod]) {
                    C[T[nod]][ind(T[nod], nod)]-= minim;
                    C[nod][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;
}