Pagini recente » Cod sursa (job #1603277) | Cod sursa (job #1091101) | Rating Kristo Krisztian (krisztian1997) | Cod sursa (job #975240) | Cod sursa (job #1874031)
#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;
struct Edge {
int from, to;
int flow, cap;
Edge(int _from = 0, int _to = 0, int _flow = 0, int _cap = 0):
from(_from), to(_to), flow(_flow), cap(_cap) {}
inline int other(int node) {
return from ^ to ^ node;
}
};
const int NMAX = 100 + 5;
vector <int> graph[NMAX * NMAX];
Edge edges[2 * 6 * NMAX * NMAX];
int father[NMAX * NMAX];
bool vis[NMAX * NMAX];
queue <int> _queue;
void addEdge(int from, int to, int cap) {
edges[m ++] = Edge(from, to, 0, cap);
edges[m ++] = Edge(to, from, 0, 0);
graph[from].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();
for (auto it: graph[node])
if (!vis[edges[it].other(node)] && edges[it].flow < edges[it].cap) {
father[edges[it].other(node)] = it;
vis[edges[it].other(node)] = true;
_queue.push(edges[it].other(node));
}
}
return vis[t];
}
int Dinic() {
int flow = 0;
while (bfs()) {
for (auto it: graph[t])
if (vis[edges[it ^ 1].other(t)] && edges[it ^ 1].flow < edges[it ^ 1].cap) {
int node = edges[it ^ 1].other(t);
int minimum = edges[it ^ 1].cap - edges[it ^ 1].flow;
while (node != s) {
minimum = min(minimum, edges[father[node]].cap - edges[father[node]].flow);
node = edges[father[node]].other(node);
}
node = edges[it ^ 1].other(t);
edges[it ^ 1].flow += minimum;
edges[it].flow -= minimum;
flow += minimum;
while (node != s) {
edges[father[node]].flow += minimum;
edges[father[node] ^ 1].flow -= minimum;
node = edges[father[node]].other(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;
}