Pagini recente » Cod sursa (job #351414) | Cod sursa (job #855) | Cod sursa (job #3176783) | Cod sursa (job #2846448) | Cod sursa (job #1873805)
#include <bits/stdc++.h>
using namespace std;
template <const int NMAX, const int MMAX>
class MaxFLow {
public:
MaxFLow() { m = 0; }
inline void setN(int _n) { n = _n; }
inline void setS(int _s) { s = _s; }
inline void setT(int _t) { t = _t; }
inline int getN() { return n; }
inline int getS() { return s; }
inline int getT() { return t; }
void clear() {
m = 0;
for (int i = 1; i <= n; ++ i)
graph[i].clear();
}
void reset() {
for (int i = 0; i < m; ++ i)
edges[i].flow = 0;
}
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);
}
inline int computeFlow() {
return Dinic();
}
private:
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;
}
};
int n, m, s, t;
vector <int> graph[NMAX];
Edge edges[2 * MMAX];
int father[NMAX];
bool vis[NMAX];
queue <int> _queue;
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;
}
};
const int NMAX = 100 + 5;
MaxFLow <NMAX * NMAX, 5 * NMAX * NMAX> f;
int N;
int a[NMAX][NMAX];
int b[NMAX][NMAX];
int c[NMAX][NMAX][4];
int sz;
int label[NMAX][NMAX];
int main()
{
ifstream 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;
f.setS(++ sz);
f.setT(++ sz);
f.setN(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];
f.addEdge(f.getS(), label[i][j], b[i][j]);
f.addEdge(label[i][j], f.getT(), a[i][j]);
if (j + 1 <= N) {
f.addEdge(label[i][j], label[i][j + 1], c[i][j][1]);
f.addEdge(label[i][j + 1], label[i][j], c[i][j][1]);
}
if (i + 1 <= N) {
f.addEdge(label[i][j], label[i + 1][j], c[i][j][2]);
f.addEdge(label[i + 1][j], label[i][j], c[i][j][2]);
}
}
cout << sum - f.computeFlow() << '\n';
return 0;
}