Pagini recente » Cod sursa (job #1917936) | Cod sursa (job #2699767) | Cod sursa (job #238511) | Cod sursa (job #886149) | Cod sursa (job #565680)
Cod sursa(job #565680)
#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;
}