Pagini recente » Cod sursa (job #2144325) | Cod sursa (job #1715047) | Cod sursa (job #2318112) | Cod sursa (job #1764223) | Cod sursa (job #1772607)
/*
* max(sum(cost_alb) + sum(cost_negru) - sum(cost_culori_distincte_adj))
* <=> min(sum(cost_culori_distincte_adj)) => taietura minima : sursa = culoarea alb, destinatie = culoarea negru
*/
#include <fstream>
#include <cstring>
using namespace std;
const int kMaxN = 100;
const int kSource = kMaxN * kMaxN;
const int kSink = kMaxN * kMaxN + 1;
const int NIL = -1;
struct Edge {
int v;
int cap;
int next;
} G[kMaxN * kMaxN * 6];
int head[kMaxN * kMaxN + 2];
int dist[kMaxN * kMaxN + 2];
int m_queue[kMaxN * kMaxN + 2];
int dinic_adj[kMaxN * kMaxN + 2];
bool breadth_first() {
int q_start = 0, q_end = 1;
m_queue[0] = kSource;
memset(dist, 0, 4 * (kMaxN * kMaxN + 2));
dist[kSource] = 1;
while (q_start != q_end) {
const int node = m_queue[q_start++];
for (int i = head[node]; i != NIL; i = G[i].next) {
const int adj_node = G[i].v;
if (G[i].cap > 0 and dist[adj_node] == 0) {
dist[adj_node] = dist[node] + 1;
m_queue[q_end++] = adj_node;
}
}
}
return dist[kSink] != 0;
}
int df(const int node, const int f_min) {
if (node == kSink or f_min == 0) {
return f_min;
}
for (; dinic_adj[node] != NIL; dinic_adj[node] = G[dinic_adj[node]].next) {
const int adj_node = G[dinic_adj[node]].v;
if (dist[adj_node] == dist[node] + 1 and G[dinic_adj[node]].cap > 0) {
const int push_flow = (f_min < G[dinic_adj[node]].cap ? f_min : G[dinic_adj[node]].cap);
const int pushed = df(adj_node, push_flow);
if (pushed > 0) {
G[dinic_adj[node]].cap -= pushed;
G[dinic_adj[node] ^ 1].cap += pushed;
return pushed;
}
}
}
return 0;
}
void add_edge(const int u, const int v,
const int cap) {
static int ptr = 0;
G[ptr].v = v;
G[ptr].cap = cap;
G[ptr].next = head[u];
head[u] = ptr++;
}
int main() {
ifstream cin("pixels.in");
ofstream cout("pixels.out");
cin.tie(0);
ios_base::sync_with_stdio(false);
int n; cin >> n;
memset(head, NIL, 4 * (kMaxN * kMaxN + 2));
int total_profit = 0;
for (int i = 0; i < n; i += 1) {
for (int j = 0; j < n; j += 1) {
int white_profit; cin >> white_profit;
add_edge(kSource, i * n + j, white_profit);
add_edge(i * n + j, kSource, 0);
total_profit += white_profit;
}
}
for (int i = 0; i < n; i += 1) {
for (int j = 0; j < n; j += 1) {
int black_profit; cin >> black_profit;
add_edge(i * n + j, kSink, black_profit);
add_edge(kSink, i * n + j, 0);
total_profit += black_profit;
}
}
for (int i = 0; i < n; i += 1) {
for (int j = 0; j < n; j += 1) {
int dir_cost[4];
for (int k = 0; k < 4; k += 1) {
cin >> dir_cost[k];
}
if (i != 0) {
add_edge(i * n + j, (i - 1) * n + j, dir_cost[0]);
add_edge((i - 1) * n + j, i * n + j, dir_cost[0]);
}
if (j != 0) {
add_edge(i * n + j, i * n + j - 1, dir_cost[3]);
add_edge(i * n + j - 1, i * n + j, dir_cost[3]);
}
}
}
int flow = 0;
while (breadth_first() == true) {
int pushed = 0;
memcpy(dinic_adj, head, 4 * (kMaxN * kMaxN + 2));
do {
pushed = df(kSource, 0x3f3f3f3f);
flow += pushed;
} while (pushed > 0);
}
cout << total_profit - flow << '\n';
return 0;
}