Pagini recente » Cod sursa (job #1996027) | Cod sursa (job #901957) | Cod sursa (job #880190) | Cod sursa (job #3276992) | Cod sursa (job #987421)
Cod sursa(job #987421)
#include <cstdio>
#include <cassert>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
const int MAX_D = 4;
const int DX[] = {-1, 0, 1, 0};
const int DY[] = {0, 1, 0, -1};
class Edge {
public:
int u, v, capacity, flow;
Edge() {}
Edge(const int u, const int v, const int capacity) {
this->u = u;
this->v = v;
this->capacity = capacity;
this->flow = 0;
}
bool Saturated() const {
return capacity == flow;
}
};
class Graph {
public:
static const int NIL = -1;
static const int oo = 0x3f3f3f3f;
int V, E;
vector< vector<int> > G;
vector<Edge> edges;
Graph(const int V = 0) {
this->V = V;
this->E = 0;
this->G = vector< vector<int> >(V, vector<int>());
this->edges = vector<Edge>();
}
void AddEdge(const Edge &edge) {
edges.push_back(edge);
G[edge.u].push_back(E);
++E;
}
int MaxFlow(const int source, const int sink) {
InitializeFlowNetwork();
vector<int> father = vector<int>(V, NIL);
int maxFlow = 0;
while (BFS(source, sink, father)) {
for (const auto &e: G[sink]) {
if (edges[NonEdge(e)].Saturated() || father[edges[e].v] == NIL)
continue;
father[sink] = NonEdge(e);
int flow = oo;
for (int x = sink; x != source; x = edges[father[x]].u)
flow = min(flow, edges[father[x]].capacity - edges[father[x]].flow);
for (int x = sink; x != source; x = edges[father[x]].u) {
edges[father[x]].flow += flow;
edges[NonEdge(father[x])].flow -= flow;
}
maxFlow += flow;
}
}
ClearResidualNetwork();
return maxFlow;
}
private:
int NonEdge(const int edgeIndex) const {
if (edgeIndex < E)
return edgeIndex + E;
return edgeIndex - E;
}
bool BFS(const int start, const int end, vector<int> &father) {
for (auto &f: father)
f = NIL;
father[start] = start;
queue<int> q;
for (q.push(start); !q.empty(); q.pop()) {
int x = q.front();
if (x == end)
continue;
for (const auto &e: G[x]) {
if (!edges[e].Saturated() && father[edges[e].v] == NIL) {
father[edges[e].v] = e;
q.push(edges[e].v);
}
}
}
return father[end] != NIL;
}
void InitializeFlowNetwork() {
edges.resize(2 * E);
for (int e = 0; e < E; ++e) {
edges[e].flow = 0;
edges[NonEdge(e)] = Edge(edges[e].v, edges[e].u, 0);
G[edges[e].v].push_back(NonEdge(e));
}
}
void ClearResidualNetwork() {
edges.resize(E);
for (int e = E - 1; e >= 0; --e)
G[edges[e].v].pop_back();
}
};
Graph G;
int N, Solution;
inline int Vertex(const int x, const int y) {
return x * N + y;
}
void Solve() {
Solution -= G.MaxFlow(N * N, N * N + 1);
}
void Read() {
assert(freopen("pixels.in", "r", stdin));
assert(scanf("%d", &N) == 1);
G = Graph(N * N + 2);
for (int x = 0; x < N; ++x) {
for (int y = 0; y < N; ++y) {
int cost;
assert(scanf("%d", &cost) == 1);
G.AddEdge(Edge(N * N, Vertex(x, y), cost));
Solution += cost;
}
}
for (int x = 0; x < N; ++x) {
for (int y = 0; y < N; ++y) {
int cost;
assert(scanf("%d", &cost) == 1);
G.AddEdge(Edge(Vertex(x, y), N * N + 1, cost));
Solution += cost;
}
}
for (int x = 0; x < N; ++x) {
for (int y = 0; y < N; ++y) {
for (int d = 0; d < MAX_D; ++d) {
int cost;
assert(scanf("%d", &cost) == 1);
int nx = x + DX[d], ny = y + DY[d];
if (0 <= nx && nx < N && 0 <= ny && ny < N)
G.AddEdge(Edge(Vertex(x, y), Vertex(nx, ny), cost));
}
}
}
}
void Print() {
assert(freopen("pixels.out", "w", stdout));
printf("%d\n", Solution);
}
int main() {
Read();
Solve();
Print();
return 0;
}