还算是比较经典了。
首先我们注意到一个性质:\(1 + 3 + \cdots + n = n ^ 2\)。所以我们可以把平方拆开。
然后容易证明 \(a_{i, j}\) 填 \(1\) 一定比填 \(0\) 不劣。
我们可以把 \(a_{i, j}\) 拆成 \(4\) 个点,然后我们想到了最小割。
构造网络:
-
\(a_{i, j, x} \leftarrow a_{i, j, x + 1}\),权重为 \(+\infty\)。
-
若 \(a_{i, j} != 0\),\(\forall x \neq a_{i, j} - 1\),\(a_{i, j, x} \rightarrow a_{i, j, x + 1}\),权重为 \(+\infty\)。
-
对于相邻的两个点 \(A, B\),\(\forall x > y, a_{A, x} \rightarrow a_{B, y}\), 权重为 \(2\)。
-
对于相邻的两个点 \(A, B\),\(\forall x, a_{A, x} \rightarrow a_{B, x}\), 权重为 \(1\)。
容易证明这个网络的最小割即为所求。
按照 Dinic 跑最大流,残量网络即为最小割。时间复杂度 \(\mathcal{O}(F\times m) = \mathcal{O}(n^4 \times d^4)\),能过。
/*******************************
| Author: DE_aemmprty
| Problem: G - Grid Coloring 2
| Contest: AtCoder - AtCoder Beginner Contest 347
| URL: https://atcoder.jp/contests/abc347/tasks/abc347_g
| When: 2024-04-02 12:29:05
|
| Memory: 1024 MB
| Time: 2000 ms
*******************************/
#include <bits/stdc++.h>
using namespace std;
long long read() {
char c = getchar();
long long x = 0, p = 1;
while ((c < '0' || c > '9') && c != '-') c = getchar();
if (c == '-') p = -1, c = getchar();
while (c >= '0' && c <= '9')
x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
return x * p;
}
const int N = 1607;
struct Edge {
int v;
long long w;
int nxt;
} e[N * N];
int n, P;
int hd[N], tot;
void add(int u, int v, long long w) {
e[++ tot] = {v, w, hd[u]};
hd[u] = tot;
}
namespace Dinic {
long long ans, dis[N], now[N];
int grp[N];
bool Build(int x, int t) {
queue <int> q;
fill(dis + 1, dis + P + 1, 2e18);
q.push(x); dis[x] = 0, now[x] = hd[x];
while (!q.empty()) {
int u = q.front(); q.pop();
if (u == t) return true;
for (int i = hd[u]; i > 1; i = e[i].nxt) {
int v = e[i].v, w = e[i].w;
if (w != 0 && dis[v] == 2e18) {
dis[v] = dis[u] + 1;
now[v] = hd[v];
q.push(v);
}
}
}
return false;
}
long long update(int x, int t, long long sum) {
if (x == t) return sum;
long long res = 0;
for (int i = now[x]; i > 1 && sum; i = e[i].nxt) {
now[x] = i;
long long v = e[i].v, w = e[i].w;
if (w > 0 && dis[v] == dis[x] + 1) {
long long p = update(v, t, min(sum, w));
if (!p) dis[v] = 2e18;
e[i].w -= p;
e[i ^ 1].w += p;
res += p;
sum -= p;
}
}
return res;
}
long long Dinic(int s, int t) {
ans = 0;
while (Build(s, t))
ans += Dinic::update(s, t, 2e18);
return ans;
}
void MinCut(int s, int t) {
for (int i = 1; i <= P; i ++)
if (dis[i] != 2e18)
grp[i] = 1;
else
grp[i] = 0;
}
void Add(int u, int v, long long w) {
add(u, v, w);
add(v, u, 0);
}
}
int a[27][27];
int col[27][27][17];
void solve() {
n = read();
for (int i = 1; i <= n; i ++) for (int j = 1; j <= n; j ++)
a[i][j] = read();
tot = 1; P = 2;
for (int i = 1; i <= n; i ++) for (int j = 1; j <= n; j ++) {
// col[i][j][0] = 1, col[i][j][5] = 2;
for (int x = 1; x <= 4; x ++) col[i][j][x] = ++ P;
}
for (int i = 1; i <= n; i ++) for (int j = 1; j <= n; j ++)
for (int x = 2; x <= 4; x ++)
Dinic::Add(col[i][j][x], col[i][j][x - 1], 2e18);
for (int i = 1; i <= n; i ++) for (int j = 1; j <= n; j ++)
if (a[i][j]) {
if (a[i][j] > 1) Dinic::Add(1, col[i][j][a[i][j] - 1], 2e18);
if (a[i][j] < 5) Dinic::Add(col[i][j][a[i][j]], 2, 2e18);
}
for (int i = 1; i <= n; i ++) for (int j = 1; j <= n; j ++)
for (int x = 1; x <= 4; x ++) for (int y = 1; y <= x; y ++) {
if (y < x) {
if (i < n) Dinic::Add(col[i][j][x], col[i + 1][j][y], 2);
if (i > 1) Dinic::Add(col[i][j][x], col[i - 1][j][y], 2);
if (j < n) Dinic::Add(col[i][j][x], col[i][j + 1][y], 2);
if (j > 1) Dinic::Add(col[i][j][x], col[i][j - 1][y], 2);
} else {
if (i < n) Dinic::Add(col[i][j][x], col[i + 1][j][x], 1);
if (i > 1) Dinic::Add(col[i][j][x], col[i - 1][j][x], 1);
if (j < n) Dinic::Add(col[i][j][x], col[i][j + 1][x], 1);
if (j > 1) Dinic::Add(col[i][j][x], col[i][j - 1][x], 1);
}
}
Dinic::Dinic(1, 2);
Dinic::MinCut(1, 2);
for (int i = 1; i <= n; i ++) {
for (int j = 1; j <= n; j ++) {
int px = 1;
for (int x = 1; x <= 4; x ++)
px += Dinic::grp[col[i][j][x]];
cout << px << ' ';
}
cout << '\n';
}
}
signed main() {
int t = 1;
while (t --) solve();
return 0;
}
标签:int,题解,long,ABC347G,Add,Dinic,col,dis
From: https://www.cnblogs.com/aemmprty/p/18111446