Pagini recente » Cod sursa (job #3218866) | Cod sursa (job #2781456) | Cod sursa (job #2792324) | Cod sursa (job #2216537) | Cod sursa (job #792180)
Cod sursa(job #792180)
#include <fstream>
#include <cstring>
#include <vector>
#include <queue>
#define x first
#define y second
using namespace std;
const int maxn = 105;
const int inf = 0x3f3f3f3f;
ifstream fin("pixels.in");
ofstream fout("pixels.out");
int S, D, A[maxn * maxn];
vector<pair<int, int> > E[maxn * maxn];
inline bool bfs() {
queue<int> Q;
Q.push(S);
memset(A, -1, sizeof(A));
A[S] = S;
while (!Q.empty()) {
int x = Q.front();
Q.pop();
if (x == D)
continue;
for (vector<pair<int, int> >::iterator it = E[x].begin(); it != E[x].end(); ++it)
if (A[it -> x] == -1 && it -> y > 0)
A[it -> x] = x, Q.push(it -> x);
}
return (A[D] != -1);
}
inline pair<int, int> &muc(int x, int y) {
if (x == S || x == D)
return E[x][y];
for (vector<pair<int, int> >::iterator it = E[x].begin(); it != E[x].end(); ++it)
if (it -> x == y)
return *it;
fout<<x<<" "<<y;
A[-500000000000LL] = 1;
}
int n, i, j, x, s, k, dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int main() {
fin >> n;
S = n * n;
D = n * n + 1;
for (i = 0; i < n; ++i)
for(j = 0; j < n; ++j)
fin >> x, E[S].push_back(make_pair(i * n + j, x)), s += x;
for (i = 0; i < n; ++i)
for (j = 0; j < n; ++j)
fin >> x, E[i * n + j].push_back(make_pair(D, x)), s += x,
E[D].push_back(make_pair(i * n + j, 0));
for (i = 0; i < n; ++i)
for (j = 0; j < n; ++j)
for (k = 0; k < 4; ++k) {
fin >> x;
if (x == 0)
continue;
if (i + dx[k] >= 0 && i + dx[k] < n && j + dy[k] >= 0 && j + dy[k] < n)
E[i * n + j].push_back(make_pair((i + dx[k]) * n + (j + dy[k]), x));
}
while (bfs())
for (vector<pair<int, int> >::iterator it = E[D].begin(); it != E[D].end(); ++it) {
if (A[it -> x] == -1)
continue;
A[D] = it -> x;
int cost = inf;
for (i = D; i != S; i = A[i])
cost = min(cost, muc(A[i], i).y);
if (cost == 0)
continue;
for (i = D; i != S; i = A[i])
if (A[i] != S)
muc(A[i], i).y -= cost, muc(i, A[i]).y += cost;
else
muc(A[i], i).y -= cost;
s -= cost;
}
fout << s << "\n";
}