G - Domino Covering SUM Editorial by en_translator
Regard the cells as vertices, and the pairs of adjacent cells as edges. Then the problem can be rephrased as follows:
The weight of two edges is defined as the sum of two integers written on the cells connected. Find the minimum possible sum of weights of edges of a matching of this graph.
The answer can be found as this minimum value subtracted from \(\displaystyle\sum _ {i,j}A _ {i,j}\).
For a bipartite graph \(G\) with non-negative edge weights, it is known that the following problem can be solved with the minimum cost flow algorithm:
Let \(f(k)\) be the minimum possible sum of edge weights of a size-\(k\) matching on \(G\). Find \(f(k)\) for each \(k=0,1,\ldots,k _ {\max}\), where \(k _ {\max}\) is the size of a maximum matching on \(G\).
Details on reduction
Add super-vertices \(S\) and \(T\). For the two maximal independent sets \(U\) and \(V\) of \(G\), add the following edges:
- an edge from \(S\) to each vertex of \(U\), of capacity \(1\) and cost \(0\);
- an edge from \(U\) to \(V\) for each edge of \(G\), of capacity \(1\) and the cost being that of the original edge;
- an edge from each vertex of \(V\) to \(T\), of capacity \(1\) and cost \(0\).
Then, \(f(k)\) is the minimum cost of a flow from \(S\) to \(T\) of flow amount \(k\).
By using the minimum cost flow algorithm, one can find \(f(k)\) for all \(k=0,1,\ldots,k _ {\max}\).
This problem can be solved with similar kind of graph, but with negative edge weights.
Define an arbitrary constant \(C\), and add \(C\) to every edge weight. Then, solve the problem above to obtain \(f(k)\), and the sought value is \(f(k)-Ck\).
Therefore, the answer is \(\displaystyle\sum _ {i,j}A _ {i,j}-\min _ {0\leq k\leq k _ {\max}}\lbrace f(k)-Ck\rbrace\).
In our problem, the amount of flow in the transformed graph is at most \(\dfrac{HW}2\), the number of edges is \(2+HW\), and the number of edges is at most \(3HW-H-W\).
The time complexity of the min_cost_slope function of AtCoder Library is \(O(F(n+m)\log(n+m))\), which is fast enough.
The following is sample code.
#include <iostream>
#include <vector>
#include <numeric>
#include <atcoder/mincostflow>
int main() {
using namespace std;
unsigned H, W;
cin >> H >> W;
vector A(H, vector<long>(W));
for (auto&& row : A)
for (auto&& a : row)
cin >> a;
atcoder::mcf_graph<int, long> graph(1 + H * W + 1);
// Add 2 × 10¹² to every edge weight to make it non-negative
constexpr long offset{2000000000000};
// Place a domino horizontally
for (unsigned i{}; i < H; ++i)
for (unsigned j{}; j + 1 < W; ++j)
if (A[i][j] + A[i][j + 1] < 0)
graph.add_edge(1 + i * W + j + ((i ^ j) & 1), 1 + i * W + j + !((i ^ j) & 1), 1, A[i][j] + A[i][j + 1] + offset);
// Place a domino vertically
for (unsigned i{}; i + 1 < H; ++i)
for (unsigned j{}; j < W; ++j)
if (A[i][j] + A[i + 1][j] < 0)
graph.add_edge(1 + (i + ((i ^ j) & 1)) * W + j, 1 + (i + !((i ^ j) & 1)) * W + j, 1, A[i][j] + A[i + 1][j] + offset);
// Edges from S, and edges from T
for (unsigned i{}; i < H; ++i)
for (unsigned j{}; j < W; ++j)
if ((i ^ j) & 1)
graph.add_edge(1 + i * W + j, 1 + H * W, 1, 0);
else
graph.add_edge(0, 1 + i * W + j, 1, 0);
long ans{};
for (const auto& [flow, cost] : graph.slope(0, 1 + H * W))
// Find min {f(k) - Ck}
ans = min(ans, cost - flow * offset);
// The sought answer is ∑ A[i][j] - min {f(k) - Ck}
cout << transform_reduce(begin(A), end(A), -ans, plus{}, [](const auto& row){return reduce(begin(row), end(row));}) << endl;
return 0;
}
posted:
last update: