G - Grid Coloring 2 解説 by en_translator
First, we can assume that \(B _ {i,j}\) does not contain \(00\) (if it does, one can show that changing those \(0\) to \(1\) does not increase the cost).
This problem can be written in the following form:
\[\min _ {B\in\lbrace{1,2,3,4,5}\rbrace ^ {\lbrace1,2,\ldots,N\rbrace ^ 2}}\sum _ x\theta _ x(B _ x)+\sum _ {x\lt y}\phi _ {x,y}(B _ x,B _ y)\]
Here,
- \(x\) and \(y\) takes \(\lbrace1,2,\ldots,N\rbrace ^ 2\), and the inequality \(x\lt y\) means \(x\) is lexicographically smaller than \(y\).
- For \(x=(i,j)\), \[\theta _ x(b)=\begin{cases}0&\quad(A _ {i,j}=0\vee b = A _ {i,j})\\+\infty&\quad(\text{otherwise.})\end{cases}\]
- For \(x=(i,j),y=(k,l)\), \[\phi _ {x,y}(b _ 1,b _ 2)=\begin{cases}0&\quad(\vert i-k\vert+\vert j-l\vert\neq1)\\ (b _ 1-b _ 2) ^ 2&\quad(\text{otherwise.})\end{cases}\]
Then, for all \(x\) and \(y\), \(\phi _ {x,y}\) is a Monge array, so this minimization problem can be solved as a minimum cut problem.
(This is the generation of so-called Project Selection Problem for \(k\)-ary variables. Detailed explanation (in Japanese) can be found in articles by tokoharu-sakura and another by noshi91.)
Specific construction of the graph
Define \((4N ^ 2+2)\) vertices: \(s,t\), and \(x _ {\gt k}\ (x\in\lbrace1,2,\ldots,N\rbrace ^ 2,k=1,2,3,4)\). Add edges as follows:
- Edge \(x _ {\gt k+1}\to x _ {\gt k}\ (1\leq k\lt4)\) with weight \(+\infty\) for all \(x\in\lbrace1,2,\ldots,N\rbrace ^ 2\)
- For \(x\) with \(A _ x\neq 0\),
- If \(1\lt A _ x\), edge \(s\to x _ {\gt A _ x-1}\) with weight \(+\infty\)
- If \(A _ x\lt 5\), edge \(x _ {\gt A _ x}\to t\) with weight \(+\infty\)
- For adjacent cells \(x\) and \(y\),
- edge \(x _ k\to y _ k\ (1\leq k\leq 4)\) with weight \(1\); and
- edge \(x _ k\to y _ l\ (1\leq l\lt k\leq 4)\) with weight \(2\).
The minimum \(s–t\) cut corresponds to the optimal solution, and its weight to the optimal cost.
First, we claim that the minimum cut does not contain an edge with weight \(+\infty\).
Proof
Let \(B _ x=\begin{cases}A _ x&\quad(A _ x\neq 0)\\1&\quad(A _ x=0)\end{cases}\), and let \(x _ {\gt k}\) included in the \(s\) side of an \(s–t\) cut if and only if \(B _ x\gt k\). Then, this cut is found to have a finite weight, which shows that an edge with weight \(+\infty\) is never included in a minimum cut.
We will assert that the graph represents the conditions in the problem statement.
Condition 1: \(B _ x\in\lbrace1,2,3,4,5\rbrace\)
Edges of the first kind constrain which of the vertices \((i,j) _ {\gt k}\) is included in the \(s\) side of the minimum cut to the following five cases:
Thus, as the figure above suggests, the vertices on the \(s\) side among \((i,j) _ {\gt k}\) determines the value \(B _ {i,j}\).
Condition 2: \(A _ x\neq0\implies A _ x=B _ x\)
Edges of the second kind forbid \(B _ x\leq A _ x-1\) and \(B _ x\gt A _ x\), ensuring \(A _ x\neq0\implies A _ x=B _ x\).
Condition 3: cost of \((B _ x-B _ y) ^ 2\)
Edges of the third kind between \(x _ {\gt k}\) and \(y _ {\gt k}\) for adjacent cells \(x\) and \(y\) contribute to the total cost by amount \((B _ x-B _ y)^2\).
It exploits \(1+3+\cdots+(2k+1)=k ^ 2\).
Thus, the problem can be solved by finding the minimum \(s–t\) cut of this graph.
Let \(0,1,\ldots,d\) be the numbers that can be written, then the graph has \((d-1)N ^ 2+2\) vertices and at most \((2d^2-3d+2)N ^ 2-(2d^2-4d+2)N\) edges. (This can be reduced by not creating vertices for those cells with determined value, but the worst cost is not affected.) Since the maximum flow is at most \(2(d-1)^2N(N-1)\), the Dinic’s algorithm with integer capacities, which costs \(O(Fm)\), bounds the overall time complexity to \(O(d^4N^4)\).
In this problem, \(d=5,N\leq20\), so this is fast enough.
The following is sample code.
#include <iostream>
#include <atcoder/maxflow>
int main() {
using namespace std;
unsigned N;
cin >> N;
atcoder::mf_graph<int> G(1 + 4 * N * N + 1);
// Boils down to S-T cut
const unsigned S = 0, T = 1 + 4 * N * N;
// Function that returns the index of vertex that corresponds to the condition: "the value written on cell (i,j) is greater than v."
const auto index{[N](unsigned i, unsigned j, unsigned v){ return (i * N + j) * 4 + v; }};
constexpr int inf = 2 * 20 * 19 * 16 + 1; // Let inf a value greater than maximum possible cos
for(unsigned i{}; i < N; ++i)
for(unsigned j{}; j < N; ++j)
for(unsigned v{1}; v + 1 <= 4; ++v)
// (i, j) is greater than v+1 ⟹ greater than v, and a penalty of +∞ is imposed if v+1 is 1 and v is 0
G.add_edge(index(i, j, v + 1), index(i, j, v), inf);
// squared difference of horizontal cells
for(unsigned i{}; i < N; ++i)
for(unsigned j{}; j + 1 < N; ++j)
for(unsigned v{1}; v <= 4; ++v){
G.add_edge(index(i, j, v), index(i, j + 1, v), 1);
G.add_edge(index(i, j + 1, v), index(i, j, v), 1);
for(unsigned u{1}; u < v; ++u){
G.add_edge(index(i, j, v), index(i, j + 1, u), 2);
G.add_edge(index(i, j + 1, v), index(i, j, u), 2);
}
}
// squareed difference of vertical cells
for(unsigned i{}; i + 1 < N; ++i)
for(unsigned j{}; j < N; ++j)
for(unsigned v{1}; v <= 4; ++v){
G.add_edge(index(i, j, v), index(i + 1, j, v), 1);
G.add_edge(index(i + 1, j, v), index(i, j, v), 1);
for(unsigned u{1}; u < v; ++u){
G.add_edge(index(i, j, v), index(i + 1, j, u), 2);
G.add_edge(index(i + 1, j, v), index(i, j, u), 2);
}
}
// cells with numbers already written on them
for(unsigned i{}; i < N; ++i)
for(unsigned j{}; j < N; ++j){
unsigned A;
cin >> A;
if(A == 0)
continue;
if(A < 5)
G.add_edge(index(i, j, A), T, inf);
if(A > 1)
G.add_edge(S, index(i, j, A - 1), inf);
}
// Flow from S and T, and find the minimum cut
G.flow(S, T);
const auto& cut{G.min_cut(S)};
for(unsigned i{}; i < N; ++i){
for(unsigned j{}; j < N; ++j){
unsigned B{1};
for(unsigned v{1}; v <= 4; ++v)
B += cut[index(i, j, v)];
cout << B << " ";
}
cout << endl;
}
return 0;
}
投稿日時:
最終更新: