题解：AT_abc407_g [ABC407G] Domino Covering SUM

CYFqwq · 2026-10-17 10:34:59 · 题解

DP，贪心好像都不行，那我们试试费用流？

建模不是很难想：

• 让源点 s 向所有 i,j 奇偶性相同的点 (i,j) 连一条流量为 1 费用为 a_{i,j} 的边；
• 让所有 i,j 奇偶性不同点 (i,j) 向汇点 t 连一条流量为 1 费用为 a_{i,j} 的边；
• 对于网格中两个相邻点 (x,y),(x',y')，不难发现这两个点中有且只有一个点的 i,j 奇偶性相同，不妨令 x,y 的奇偶性相同，让 (x,y) 向 (x',y') 连一条流量为 1 费用为 0 的边。

为什么这么建模？考虑一条路径，会流过 s\to (x,y)\to (x',y')\to t，花费 a_{x,y}+a_{x',y'}，相当于放了一个骨牌。流量为 1 保证了一个点不会被覆盖多次。我们求最小费用流就能得到被骨牌覆盖的点权最小值 \mathrm{ans}，用总点权减去 \mathrm{ans} 就是最终答案。

最小费用流怎么求呢？我们不断找总费用最小的增广路，如果费用 <0 就增广，否则就停止即可（你问我为什么对？我也不知道）。

复杂度 O((hw)^3)，实际上费用流很难跑满，可以通过。

#include<bits/stdc++.h>
#define int long long
using namespace std;

int cnt = 1;
const int N = 2010;
const int inf = 1e18;
struct node { int v, w, c; } e[N];
vector<node> g[N];
int val[N*20], dis[N], vis[N], a[N][N], id[N][N];

void add(int u, int v, int w, int c) {
    g[u].push_back({v, ++cnt, c});
    val[cnt] = w;
    g[v].push_back({u, ++cnt, -c});
}

bool bfs(int s, int t) {
    memset(dis, 0x3f, sizeof(dis));
    queue<int> q;
    q.push(s);
    dis[s] = 0;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        vis[u] = 0;
        for (auto [v, w, c] : g[u]) {
            if (!val[w]) continue;
            if (dis[v] > dis[u] + c) {
                dis[v] = dis[u] + c;
                e[v] = {u, w, c};
                if (!vis[v]) q.push(v);
                vis[v] = 1;
            }
        }
    }
    return dis[t] < dis[0];
}

signed main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n, m;
    cin >> n >> m;
    int s = n*m+1, t = n*m+2, sum = 0, ans = 0;
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) id[i][j] = (i-1)*m+j;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
            sum += a[i][j];
            if ((i & 1) == (j & 1)) {
                add(s, id[i][j], 1, a[i][j]);
                if (i > 1) add(id[i][j], id[i-1][j], 1, 0);
                if (i < n) add(id[i][j], id[i+1][j], 1, 0);
                if (j > 1) add(id[i][j], id[i][j-1], 1, 0);
                if (j < m) add(id[i][j], id[i][j+1], 1, 0);
            } else {
                add(id[i][j], t, 1, a[i][j]);
            }
        }
    }
    while (bfs(s, t) && dis[t] < 0) {
        int u = t, f = inf;
        while (e[u].v) f = min(f, val[e[u].w]), u = e[u].v;
        ans += f * dis[t], u = t;
        while (e[u].v) val[e[u].w] -= f, val[e[u].w^1] += f, u = e[u].v;
    } 
    cout << sum-ans;
    return 0;
}