Pagini recente » Cod sursa (job #1958517) | Cod sursa (job #425398) | Cod sursa (job #530203) | Cod sursa (job #984178) | Cod sursa (job #565686)
Cod sursa(job #565686)
#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;
}