Pagini recente » Cod sursa (job #404544) | Cod sursa (job #2856652) | Cod sursa (job #2415571) | Cod sursa (job #178835) | Cod sursa (job #2029446)
#include <bits/stdc++.h>
#define maxN 102
#define maxD 10004
#define mp make_pair
#define pii pair < int, int >
#define fi first
#define sec second
#define inf 1000000000
using namespace std;
FILE *fin = freopen("pixels.in", "r", stdin);
FILE *fout = freopen("pixels.out", "w", stdout);
int n, a[maxN][maxN], b[maxN][maxN], c[maxN][maxN][4];
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
int Nod[maxN][maxN];
/* ------------- MaxFlow ------------ */
int idx, S, D;
pii deUnde[maxD];
queue < int > Q;
vector < pair < int, int > > G[maxD];
int r[maxD * 8], P[maxD * 8];
int ans;
void BFS(int S, int D)
{
for (int i = 0; i <= D; ++ i)
deUnde[i] = mp(-1, -1);
Q.push(S);
deUnde[S] = mp(S, 0);
deUnde[D] = mp(D, 0);
while (!Q.empty())
{
int x = Q.front();
Q.pop();
for (pii i : G[x])
if (r[i.sec] > 0 && deUnde[i.fi].fi == -1)
{
deUnde[i.fi] = mp(x, i.sec);
Q.push(i.fi);
}
}
}
int maxFlow()
{
int ret = 0;
bool continua = true;
while (continua)
{
BFS(S, D);
continua = false;
for(pii u : G[D])
if (r[u.sec] > 0 && deUnde[u.fi].fi != -1 && u.fi != D)
{
continua = true;
deUnde[D] = u;
int nod = D;
int cap = inf;
while (nod != S)
{
cap = min(cap, r[deUnde[nod].sec]);
nod = deUnde[nod].fi;
}
nod = D;
ret += cap;
while (nod != S)
{
r[deUnde[nod].sec] -= cap;
r[P[deUnde[nod].sec]] += cap;
nod = deUnde[nod].fi;
}
}
}
return ret;
}
void compNet()
{
D = n * n + 1;
for (int i = 1; i <= n; ++ i)
for (int j = 1; j <= n; ++ j)
{
G[Nod[i][j]].push_back(mp(S, ++ idx));
G[S].push_back(mp(Nod[i][j], ++ idx));
r[idx] = r[idx - 1] = a[i][j];
P[idx] = idx - 1;
P[idx - 1] = idx;
G[Nod[i][j]].push_back(mp(D, ++ idx));
G[D].push_back(mp(Nod[i][j], ++ idx));
r[idx] = r[idx - 1] = b[i][j];
P[idx] = idx - 1;
P[idx - 1] = idx;
}
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; ++ i)
for (int j = 1; j <= n; ++ j)
scanf("%d", &a[i][j]);
for (int i = 1; i <= n; ++ i)
for (int j = 1; j <= n; ++ j)
{
scanf("%d", &b[i][j]);
ans += a[i][j] + b[i][j];
Nod[i][j] = ++ idx;
}
idx = 0;
for (int i = 1; i <= n; ++ i)
for (int j = 1; j <= n; ++ j)
for (int t = 0; t < 4; ++ t)
{
scanf("%d", &c[i][j][t]);
if (c[i][j][t] && t > 1)
{
//r[mp(Nod[i][j], Nod[i + dx[t]][j + dy[t]])] =
// r[mp(Nod[i + dx[t]][j + dy[t]], Nod[i][j])] = c[i][j][t];
G[Nod[i][j]].push_back(mp(Nod[i + dx[t]][j + dy[t]], ++ idx));
G[Nod[i + dx[t]][j + dy[t]]].push_back(mp(Nod[i][j], ++ idx));
P[idx] = idx - 1;
P[idx - 1] = idx;
r[idx] = r[idx - 1] = c[i][j][t];
}
}
compNet();
printf("%d\n", ans - maxFlow());
return 0;
}