Pagini recente » Cod sursa (job #833240) | Cod sursa (job #2754333) | Cod sursa (job #1214291) | Cod sursa (job #538618) | Cod sursa (job #1874048)
#include <bits/stdc++.h>
using namespace std;
class InputReader {
public:
InputReader() {}
InputReader(const char *file_name) {
input_file = fopen(file_name, "r");
cursor = 0;
fread(buffer, SIZE, 1, input_file);
}
inline InputReader &operator >>(int &n) {
while(buffer[cursor] < '0' || buffer[cursor] > '9') {
advance();
}
n = 0;
while('0' <= buffer[cursor] && buffer[cursor] <= '9') {
n = n * 10 + buffer[cursor] - '0';
advance();
}
return *this;
}
private:
FILE *input_file;
static const int SIZE = 1 << 17;
int cursor;
char buffer[SIZE];
inline void advance() {
++ cursor;
if(cursor == SIZE) {
cursor = 0;
fread(buffer, SIZE, 1, input_file);
}
}
};
//MaxFlow
int n, m, s, t;
const int NMAX = 100 + 5;
int from[12 * NMAX * NMAX], to[12 * NMAX * NMAX];
int cap[12 * NMAX * NMAX];
inline int other(int edge, int node) {
return from[edge] ^ to[edge] ^ node;
}
vector <int> graph[NMAX * NMAX];
int father[NMAX * NMAX];
bool vis[NMAX * NMAX];
queue <int> _queue;
void addEdge(int frm, int _to, int cp) {
from[m] = frm;
to[m] = _to;
cap[m ++] = cp;
from[m] = _to;
to[m ++] = frm;
graph[frm].push_back(m - 2);
graph[_to].push_back(m - 1);
}
bool bfs() {
memset(vis, 0, (n + 1) * sizeof(bool));
vis[s] = true;
_queue.push(s);
int node;
while (!_queue.empty()) {
node = _queue.front();
_queue.pop();
if (node == t)
continue;
for (auto it: graph[node])
if (!vis[other(it, node)] && cap[it]) {
father[other(it, node)] = it;
vis[other(it, node)] = true;
_queue.push(other(it, node));
}
}
return vis[t];
}
int Dinic() {
int flow = 0;
while (bfs()) {
for (auto it: graph[t])
if (vis[other(it ^ 1, t)] && cap[it ^ 1]) {
int node = other(it ^ 1, t);
int minimum = cap[it ^ 1];
while (node != s) {
minimum = min(minimum, cap[father[node]]);
node = other(father[node], node);
}
node = other(it ^ 1, t);
cap[it ^ 1] -= minimum;
cap[it] += minimum;
flow += minimum;
while (node != s) {
cap[father[node]] -= minimum;
cap[father[node] ^ 1] += minimum;
node = other(father[node], node);
}
}
}
return flow;
}
int N;
int a[NMAX][NMAX];
int b[NMAX][NMAX];
int c[NMAX][NMAX][4];
int sz;
int label[NMAX][NMAX];
int main()
{
InputReader cin("pixels.in");
ofstream cout("pixels.out");
cin >> N;
for (int i = 1; i <= N; ++ i)
for (int j = 1; j <= N; ++ j)
cin >> a[i][j];
for (int i = 1; i <= N; ++ i)
for (int j = 1; j <= N; ++ j)
cin >> b[i][j];
for (int i = 1; i <= N; ++ i)
for (int j = 1; j <= N; ++ j)
for (int k = 0; k < 4; ++ k)
cin >> c[i][j][k];
for (int i = 1; i <= N; ++ i)
for (int j = 1; j <= N; ++ j)
label[i][j] = ++ sz;
s = ++ sz;
t = ++ sz;
n = sz;
int sum = 0;
for (int i = 1; i <= N; ++ i)
for (int j = 1; j <= N; ++ j) {
sum += a[i][j] + b[i][j];
addEdge(s, label[i][j], b[i][j]);
addEdge(label[i][j], t, a[i][j]);
if (j + 1 <= N) {
addEdge(label[i][j], label[i][j + 1], c[i][j][1]);
addEdge(label[i][j + 1], label[i][j], c[i][j][1]);
}
if (i + 1 <= N) {
addEdge(label[i][j], label[i + 1][j], c[i][j][2]);
addEdge(label[i + 1][j], label[i][j], c[i][j][2]);
}
}
cout << sum - Dinic() << '\n';
return 0;
}