Pagini recente » Cod sursa (job #1274541) | Cod sursa (job #1059199) | Cod sursa (job #2919217) | Cod sursa (job #1827868) | Cod sursa (job #1759815)
#include <fstream>
#include <queue>
#include <cstring>
#include <set>
using namespace std;
ifstream cin("pixels.in");
ofstream cout("pixels.out");
const int MAXN = 100;
const int INF = 1000000000;
int code[1 + MAXN][1 + MAXN];
int source, sink;
int line[] = {-1, 0, 1, 0};
int column[] = {0, 1, 0, -1}, edges = 0;
vector<int> g[1 + MAXN * MAXN + 1];
int where[1 + 8 * MAXN * MAXN], capacity[1 + 8 * MAXN * MAXN];
int dad[1 + MAXN + 1];
void AddEdge(int from, int to, int value, int inverted) {
edges++;
where[edges] = to;
capacity[edges] = value;
g[from].push_back(edges);
edges++;
where[edges] = from;
capacity[edges] = inverted;
g[to].push_back(edges);
}
int f(int x) {
if (x & 1)
return x + 1;
return x - 1;
}
bool BFS() {
queue<int> Queue;
memset(dad, -1, sizeof(dad));
Queue.push(source);
dad[source] = 0;
while (!Queue.empty()) {
int node = Queue.front();
Queue.pop();
for (auto &son : g[node])
if (dad[where[son]] == -1 && capacity[son] > 0) {
dad[where[son]] = son;
Queue.push(where[son]);
if (where[son] == sink)
return true;
}
}
return false;
}
int MaximumFlow() {
int answer = 0;
while (BFS())
for (auto &node : g[sink])
if (capacity[f(node)] && dad[where[node]] != -1) {
int add = INF;
for (int node = sink; node != source; node = where[f(dad[node])])
if (capacity[dad[node]] < add)
add = capacity[dad[node]];
answer += add;
for (int node = sink; node != source; node = where[f(dad[node])]) {
capacity[dad[node]] -= add;
capacity[f(dad[node])] += add;
}
}
return answer;
}
int main() {
int n, answer = 0;
cin >> n;
source = 0;
sink = n * n + 1;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) {
code[i][j] = (i - 1) * n + j;
int value;
cin >> value;
answer += value;
AddEdge(source, code[i][j], value, 0);
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) {
int value;
cin >> value;
answer += value;
AddEdge(code[i][j], sink, value, 0);
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
for (int k = 0; k < 4; k++) {
int value;
cin >> value;
if (code[i][j] < code[i + line[k]][j + column[k]])
AddEdge(code[i][j], code[i + line[k]][j + column[k]], value, value);
}
cout << answer - MaximumFlow() << "\n";
return 0;
}