Pagini recente » Cod sursa (job #2297208) | Cod sursa (job #455574) | Cod sursa (job #924466) | Cod sursa (job #2010389) | Cod sursa (job #2029441)
#include <bits/stdc++.h>
#define maxN 102
#define maxD 10002
#define mp make_pair
#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 idx, Nod[maxN][maxN];
/* ------------- MaxFlow ------------ */
int S, D, deUnde[maxD];
queue < int > Q;
vector < int > G[maxD];
map < pair < int, int >, int > r;
int ans;
void BFS(int S, int D)
{
memset(deUnde, -1, sizeof(deUnde));
Q.push(S);
deUnde[S] = S;
deUnde[D] = D;
while (!Q.empty())
{
int x = Q.front();
Q.pop();
for (int i : G[x])
if (r[mp(x, i)] > 0 && deUnde[i] == -1)
{
deUnde[i] = x;
Q.push(i);
}
}
}
int maxFlow()
{
int ret = 0;
bool continua = true;
while (continua)
{
BFS(S, D);
continua = false;
for(int u : G[D])
if (r[mp(u, D)] > 0 && deUnde[u] != -1 && u != D)
{
continua = true;
deUnde[D] = u;
int nod = D;
int cap = inf;
while (nod != S)
{
cap = min(cap, r[mp(deUnde[nod], nod)]);
nod = deUnde[nod];
}
nod = D;
ret += cap;
while (nod != S)
{
r[mp(deUnde[nod], nod)] -= cap;
r[mp(nod, deUnde[nod])] += cap;
nod = deUnde[nod];
}
}
}
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(S);
G[S].push_back(Nod[i][j]);
r[mp(S, Nod[i][j])] = a[i][j];
G[Nod[i][j]].push_back(D);
G[D].push_back(Nod[i][j]);
r[mp(Nod[i][j], D)] = b[i][j];
}
}
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;
}
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(Nod[i + dx[t]][j + dy[t]]);
G[Nod[i + dx[t]][j + dy[t]]].push_back(Nod[i][j]);
}
}
compNet();
printf("%d\n", ans - maxFlow());
return 0;
}