Pagini recente » Cod sursa (job #853079) | Monitorul de evaluare | Cod sursa (job #2106783) | Cod sursa (job #2841637) | Cod sursa (job #1900846)
#include <fstream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <queue>
const int kMaxDim = 105;
struct Edge {
int from, to, capacity;
};
int a[kMaxDim][kMaxDim], b[kMaxDim][kMaxDim], c[kMaxDim][kMaxDim][4], nodeTag[kMaxDim][kMaxDim];
int edgeCount;
Edge edges[10 * kMaxDim * kMaxDim];
std::vector< int > adjList[kMaxDim * kMaxDim];
void AddDirectedEdge(int from, int to, int capacity) {
edges[edgeCount].from = from;
edges[edgeCount].to = to;
edges[edgeCount].capacity = capacity;
edgeCount++;
adjList[from].push_back(edgeCount - 1);
edges[edgeCount].from = to;
edges[edgeCount].to = from;
edges[edgeCount].capacity = 0;
edgeCount++;
adjList[to].push_back(edgeCount - 1);
}
void AddUnDirectedEdge(int first, int second, int capacity) {
edges[edgeCount].from = first;
edges[edgeCount].to = second;
edges[edgeCount].capacity = capacity;
edgeCount++;
adjList[first].push_back(edgeCount - 1);
edges[edgeCount].from = second;
edges[edgeCount].to = first;
edges[edgeCount].capacity = capacity;
edgeCount++;
adjList[second].push_back(edgeCount - 1);
}
bool visited[kMaxDim * kMaxDim];
int backEdge[kMaxDim * kMaxDim];
std::queue< int > que;
bool Bfs(int source, int destination) {
memset(visited, false, sizeof visited);
que.push(source);
visited[source] = true;
while (!que.empty()) {
int curr = que.front();
que.pop();
if (curr == destination)
continue;
for (int edge : adjList[curr]) {
if (edges[edge].capacity == 0 || visited[ edges[edge].to ])
continue;
backEdge[ edges[edge].to ] = edge;
visited[ edges[edge].to ] = true;
que.push( edges[edge].to );
}
}
return visited[destination];
}
int GetMaxFlow(int source, int destination) {
int maxFlow = 0;
while (Bfs(source, destination)) {
for (int finalEdge : adjList[destination]) {
if (!visited[ edges[finalEdge].to ] || edges[finalEdge ^ 1].capacity == 0)
continue;
backEdge[destination] = (finalEdge ^ 1);
int addFlow = 0x3f3f3f3f;
for (int node = destination; node != source; node = edges[ backEdge[node] ].from)
addFlow = std::min(addFlow, edges[ backEdge[node] ].capacity);
if (addFlow == 0)
continue;
maxFlow += addFlow;
for (int node = destination; node != source; node = edges[ backEdge[node] ].from) {
edges[ backEdge[node] ].capacity -= addFlow;
edges[ backEdge[node] ^ 1 ].capacity += addFlow;
}
}
}
return maxFlow;
}
int main() {
std::ifstream inputFile("pixels.in");
std::ofstream outputFile("pixels.out");
int n;
inputFile >> n;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
inputFile >> a[i][j];
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
inputFile >> b[i][j];
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
for (int k = 0; k < 4; ++k)
inputFile >> c[i][j][k];
int count = 0;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
nodeTag[i][j] = ++count;
int source = ++count;
int destination = ++count;
int sum = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
sum += a[i][j] + b[i][j];
AddDirectedEdge(source, nodeTag[i][j], a[i][j]);
AddDirectedEdge(nodeTag[i][j], destination, b[i][j]);
if (i + 1 <= n)
AddUnDirectedEdge(nodeTag[i][j], nodeTag[i + 1][j], c[i][j][2]);
if (j + 1 <= n)
AddUnDirectedEdge(nodeTag[i][j], nodeTag[i][j + 1], c[i][j][1]);
}
}
outputFile << sum - GetMaxFlow(source, destination) << '\n';
inputFile.close();
outputFile.close();
return 0;
}
//Trust me, I'm the Doctor!