Cod sursa(job #565669)

Utilizator katakunaCazacu Alexandru katakuna Data 28 martie 2011 09:24:21
Problema Pixels Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.15 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], viz[Nmax * Nmax];
vector < pair <int, int> > V[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 ( make_pair (n * i + j, cst) );
            V[n * i + j].push_back ( make_pair (S, cst) );
            //printf ("%d %d %d\n", S, n * i + j, cst);
        }

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

int bfs () {

    int p, u, nod, ok = 0;
    int Q[Nmax * Nmax];
    vector < pair <int, 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->first] && it->second > 0) {
                if (it->first == D) {ok = 1; continue;}
                viz[it->first] = 1;
                T[it->first] = nod;
                Q[++u] =it->first;
            }
        }
    }

    return ok;
}

int muchie (int x, int y) {

    for (vector < pair <int, int> >::iterator it = V[x].begin (); it != V[x].end (); it++)
        if (it->first == y) return it->second;

    return 0;
}

void mod_muchie (int x, int y, int val) {

    for (vector < pair <int, int> >::iterator it = V[x].begin (); it != V[x].end (); it++)
        if (it->first == y) {
            it->second+= val;
            return ;
        }
}

void rezolva () {

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

    while (bfs ()) {

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

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