Pagini recente » Cod sursa (job #2988538) | Cod sursa (job #564994) | Cod sursa (job #2622065) | Cod sursa (job #1161304) | Cod sursa (job #1418607)
#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
int N, ans, cod[109][109];
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
int nr, S, D, t[10009];
vector < int > v[10009];
int M, F[120009], C[120009], y[120009];////edges
void add_edge (int left, int right, int cap)
{
y[++M] = right, C[M] = cap, F[M] = 0, v[left].push_back (M);
y[++M] = left, C[M] = 0, F[M] = 0, v[right].push_back (M);
}
int rev (int M)
{
if (M & 1)
return M + 1;
return M - 1;
}
bool bfs ()
{
queue < int > cc;
for (int i=1; i<=nr; i++)
t[i] = -1;
cc.push (S);
t[S] = 0;
while (!cc.empty())
{
int nod = cc.front ();
cc.pop();
for (vector < int > :: iterator it = v[nod].begin(); it != v[nod].end(); it ++)
if (t[y[*it]] == -1 && F[*it] < C[*it])
{
t[y[*it]] = *it;
cc.push (y[*it]);
if (y[*it] == D)
return 1;
}
}
return 0;
}
int flux ()
{
int sol = 0;
while (bfs ())
{
for (vector < int > :: iterator it = v[D].begin(); it != v[D].end(); it ++)
if (F[rev(*it)] < C[rev(*it)] && t[y[*it]] != -1)
{
int mini = 1000000;
t[D] = rev(*it);
for (int i=D; i != S; i = y[rev(t[i])])
{
if (C[t[i]] - F[t[i]] < mini)
mini = C[t[i]] - F[t[i]];
}
sol += mini;
for (int i=D; i != S; i = y[rev(t[i])])
{
F[t[i]] += mini;
F[rev(t[i])] -= mini;
}
}
}
return sol;
}
int main()
{
freopen ("pixels.in", "r", stdin);
freopen ("pixels.out", "w", stdout);
scanf ("%d", &N);
S = 1;
D = nr = 2;
for (int i=1; i<=N; i++)
for (int j=1; j<=N; j++)
{
cod[i][j] = ++nr;
int x;
scanf ("%d", &x);
ans += x;
add_edge (S, cod[i][j], x);
}
for (int i=1; i<=N; i++)
for (int j=1; j<=N; j++)
{
int x;
scanf ("%d", &x);
ans += x;
add_edge (cod[i][j], D, x);
}
for (int i=1; i<=N; i++)
for (int j=1; j<=N; j++)
for (int k=0; k<4; k++)
{
int x;
scanf ("%d", &x);
if (i + dx[k] >= 1 && j + dy[k] >= 1 && i + dx[k] <= N && j + dy[k] <= N)
add_edge (cod[i][j], cod[i+dx[k]][j+dy[k]], x);
}
printf ("%d\n", ans - flux ());
return 0;
}