3141. 「BJWC2018」Kakuro - 题解

题目概览

问题类型：最小费用流 + 网络流建模
核心难度：⭐⭐⭐⭐⭐⭐⭐⭐ (8/10)
关键技巧：用流量表示数字的最终值，用分段线性函数处理绝对值代价

一句话题意

给定一个 Kakuro 棋盘（包含线索和空格），每个数字可以修改但有代价，求使所有约束满足的最小代价。

关键约束

1. 空格必须填正整数
2. 横向线索 = 右侧连续空格之和
3. 纵向线索 = 下方连续空格之和
4. 修改数字 $x$ 一个单位的代价为 $c_x$
5. 部分数字不可修改（代价为 $\infty$）

---

算法流程概览

输入数据
   ↓
建立网络图模型
├─ 纵向线索节点（从源点获取流量）
├─ 横向线索节点（向汇点输出流量）
└─ 空格作为边连接上述节点
   ↓
处理初始偏差
├─ 计算每个数字到其下界的代价
└─ 用负费用边强制回到可行域
   ↓
最小费用流求解
├─ SPFA 寻找最小费用增广路
└─ DFS 沿最短路增广
   ↓
可行性检查
├─ 检查不可修改的数字是否被强制修改
└─ 若违反约束则输出 -1
   ↓
输出答案：初始偏差代价 + 流量代价

---

题目分析

这是一道经典的最小费用流问题，核心在于将 Kakuro 游戏的约束条件转化为网络流模型。

为什么是网络流？

观察1：线索的约束本质上是"和"的约束
→ 可以用流量守恒表示

观察2：修改数字有线性代价
→ 可以用边的费用表示

观察3：每个空格同时受两个线索约束
→ 空格是"纵向流"转"横向流"的桥梁

---

数学建模

问题抽象

给定一个 Kakuro 棋盘，包含：

• 线索数字：横向线索（右上角）和纵向线索（左下角）
• 空格：需要填入正整数
• 修改代价：每个数字有一个代价 $c_i$，修改 $\Delta$ 单位需要花费 $c_i \times |\Delta|$

目标：找到最小代价，使得所有约束满足：

1. 空格中的数字为正整数
2. 每个横向线索等于其右侧连续空格之和
3. 每个纵向线索等于其下方连续空格之和

核心观察

这是一个带费用的可行流问题：

• 每个数字可以看作一个"流量"
• 线索的约束等价于"流量守恒"
• 修改代价可以用边的费用函数表示

---

算法设计

网络流建模

节点设计

建立以下节点：

1. 源点 $S$
2. 汇点 $T$
3. 纵向线索节点：对于每个纵向线索（左下角），建立一个节点
4. 横向线索节点：对于每个横向线索（右上角），建立一个节点

建模示例

考虑一个简单的 3×3 Kakuro：

   [17]  [ ]   [ ]
   [ ]   [a]  [b]
   [ ]   [c]  [d]

其中 [17] 是左下角线索，表示下方两个空格 $a, c$ 的和为 17。

网络建模：

    源点 S
      ↓ (流量 = 线索值17)
   [线索17]
    ↙   ↘
  [a]   [c]  (边的流量 = 空格的值)
    ↘   ↙
   [横向线索节点]
      ↓
    汇点 T

流量守恒：

• 从 $S$ 流出的总流量 = 所有纵向线索的和
• 流入 $T$ 的总流量 = 所有横向线索的和
• 每个空格的流量 = 该空格的最终值

---

边的设计

关键思想：将每个数字的修改代价建模为分段线性费用函数。

对于每个可修改的数字 $x$，当前值为 $a$，代价系数为 $c$：

• 修改到 $y$ 的代价为 $c \times |y - a|$

在网络流中，我们使用流量表示数字的最终值。

1. 纵向线索的建模

对于纵向线索节点 $u$（初始值为 $a$，下方有 $k$ 个空格）：

• 目标流量：该节点需要向下输出总流量等于最终的线索值

• 初始偏差处理：

  • 如果 $a > k$（初始值大于下方空格数），说明即使每个空格填 1，总和也无法达到 $a$
  • 需要强制从源点流入 $(a - k)$ 单位流量，费用为 $-c$（负费用表示"回退"到可行域）
  • 边：$S \to u$，容量 $(a - k)$，费用 $-c$

• 增加流量：允许从源点额外流入任意流量（对应增加线索值）

  • 边：$S \to u$，容量 $+\infty$，费用 $+c$

2. 横向线索的建模

对于横向线索节点 $v$（初始值为 $a$，右侧有 $k$ 个空格）：

• 目标流量：该节点需要接收总流量等于最终的线索值

• 初始偏差处理：

  • 如果 $a > k$，需要强制流出 $(a - k)$ 单位到汇点
  • 边：$v \to T$，容量 $(a - k)$，费用 $-c$

• 增加流量：允许向汇点额外流出任意流量

  • 边：$v \to T$，容量 $+\infty$，费用 $+c$

3. 空格的建模

对于空格 $(i, j)$（初始值为 $b$，上方纵向线索节点为 $u$，左侧横向线索节点为 $v$）：

• 流量含义：从 $u$ 流向 $v$ 的流量表示该空格的最终值

• 下界约束：空格必须 $\geq 1$

• 初始偏差处理：

  • 如果 $b > 1$，需要保证至少流过 $(b - 1)$ 单位
  • 边：$u \to v$，容量 $(b - 1)$，费用 $-c$

• 增加流量：允许额外流量

  • 边：$u \to v$，容量 $+\infty$，费用 $+c$

费用函数的巧妙设计

这里使用了一个关键技巧：将绝对值费用函数分解为两条边。

对于数字 $x$（当前值 $a$，代价系数 $c$）：

$$\text{Cost}(y) = c \times |y - a| = \begin{cases} c \times (a - y) & y < a \\ c \times (y - a) & y \geq a \end{cases} $$

在网络流中：

1. 强制边（费用 $-c$）：处理从 $a$ 减少到下界的部分
2. 弹性边（费用 $+c$）：处理从下界增加的部分

总代价 = 初始偏差代价 + 网络流费用

可行性判断

网络流求解后，需要检查：

• 所有费用为 $-\infty$ 的边（不可修改的数字产生的强制边）必须满流
• 如果存在未满足的强制约束，说明无解

---

算法实现细节

1. 节点编号

// 为每个线索分配唯一编号
if (op[i][j] & 1) {  // 纵向线索（左下角）
    id[0][i][j] = ++tot;
}
if (op[i][j] & 2) {  // 横向线索（右上角）
    id[1][i][j] = ++tot;
}

2. 连续空格的关联

// 将每个空格关联到其对应的线索节点
FOR(i, 1, n) {
    FOR(j, 1, m) {
        if (id[0][i][j]) {  // 纵向线索
            FOR(k, i + 1, n) {
                if (op[k][j] != 4) break;  // 遇到非空格停止
                id0[k][j] = id[0][i][j];   // 空格(k,j)属于线索(i,j)
                v[0][i][j]++;              // 统计空格数量
            }
        }
        // 横向线索同理
    }
}

3. 建边策略

对于每个数字，计算初始偏差：

// 纵向线索：v[0][i][j] 是下方空格数，a[0][i][j] 是线索值
ans += val * abs(v[0][i][j] - a[0][i][j]);  // 累加强制偏差代价

if (a[0][i][j] > v[0][i][j]) {
    // 强制流入，保证最小可行性
    add(s, id[0][i][j], a[0][i][j] - v[0][i][j], -val);
}
// 弹性流入，允许增加
add(s, id[0][i][j], inf, val);

4. 最小费用流算法

使用 SPFA + Dinic 实现：

• SPFA：寻找最短路（最小费用路径）
• DFS：沿最小费用路径增广
• 复杂度：$O(nmf)$，其中 $f$ 是流量

5. 可行性检查

bool check() {
    for (int i = 0; i < etot; i += 2) {
        // 检查费用为 inf 的强制边是否满流
        if (e[i].co == inf && e[i^1].w > 0) return 0;  // 反向边有剩余容量
        if (e[i].co == -inf && e[i].w > 0) return 0;   // 正向边未满流
    }
    return 1;
}

---

复杂度分析

时间复杂度

• 节点数：$O(nm)$（每个格子最多 2 个节点）
• 边数：$O(nm)$（每个数字对应常数条边）
• 最小费用流：$O(VE \times f)$，其中 $f$ 是总流量
  • 对于本题：$f = O(nm \times 10^6)$
  • 实际运行时：SPFA 优化后约 $O(nm \times \text{平均增广次数})$

总复杂度：$O(n^2m^2 \times W)$，其中 $W$ 是数字范围

空间复杂度

• 网络：$O(nm)$ 个节点，$O(nm)$ 条边
• 总空间：$O(nm)$

---

算法优化

代码中的优化技巧

1. 当前弧优化：cur[u] 记录当前节点的搜索位置，避免重复搜索
2. 访问标记：vis[] 防止同一轮 DFS 中重复访问
3. 距离重置：dis[v] = 0 剪枝不可达节点
4. 负费用优先：SPFA 优先处理负费用边，快速找到可行流

---

数学理论基础

为什么这样建模是正确的？

定理1：流量与数字值的等价性

命题：在最优解中，边 $e$ 的流量 $f(e)$ 等于对应数字的最终值。

证明：

设空格 $(i,j)$ 对应边 $e: u \to v$，其中 $u$ 是纵向线索节点，$v$ 是横向线索节点。

根据建边规则：

• $u$ 的出流 = 下方所有空格的流量和
• $v$ 的入流 = 左侧所有空格的流量和

由流量守恒：

$$\sum_{k: \text{下方空格}} f(e_k) = \text{纵向线索值}$$ $$\sum_{k: \text{右侧空格}} f(e_k) = \text{横向线索值}$$

这恰好对应原问题的约束条件。□

---

定理2：费用函数的等价性

命题：总费用 = $\sum_i c_i |x_i^{\text{final}} - x_i^{\text{init}}|$

证明：

对于数字 $i$，初始值 $a_i$，最终值 $x_i$，下界 $l_i$，代价系数 $c_i$：

情况1：$x_i < a_i$（减少）

网络中建立的边：

• 边1：容量 $(a_i - l_i)$，费用 $-c_i$
• 边2：容量 $\infty$，费用 $+c_i$

最优策略：

1. 先用边1流 $(a_i - x_i)$ 单位，费用 $-c_i(a_i - x_i)$
2. 剩余 $(x_i - l_i)$ 单位通过边2，费用 $+c_i(x_i - l_i)$

总费用：

$$c_i|a_i - l_i| + (-c_i)(a_i - x_i) + c_i(x_i - l_i) = c_i|a_i - x_i| $$

情况2：$x_i > a_i$（增加）

类似分析可得总费用 = $c_i(x_i - a_i)$。□

---

定理3：最优性保证

命题：最小费用流的解对应原问题的最优解。

证明要点：

1. 凸性：每个数字的费用函数 $f(x) = c|x - a|$ 是凸函数
2. 线性约束：和的约束是线性的
3. 整数性：网络流的约束矩阵具有全幺模性，保证最优解是整数

根据凸优化理论，凸目标函数在线性约束下的最优解存在且唯一（若可行域非空）。

最小费用流算法通过逐步增广最小费用路径，等价于求解线性规划的对偶问题，因此能得到全局最优解。□

---

正确性证明

定理：该建模与原问题等价

证明：

1. 流量守恒 ⟺ 和的约束

   • 纵向线索节点的出流 = 下方所有空格的流量和 = 线索值
   • 横向线索节点的入流 = 左侧所有空格的流量和 = 线索值

2. 费用函数 ⟺ 修改代价

   • 初始偏差代价：$\sum c_i \times |\text{initial\_deviation}|$
   • 网络流费用：$\sum c_i \times |\text{additional\_change}|$
   • 总代价 = 初始偏差代价 + 网络流费用 = $\sum c_i \times |y_i - a_i|$

3. 可行性 ⟺ 强制边满流

   • 代价为 $-\infty$ 的边对应不可修改的数字
   • 这些边必须满流才能保证原约束满足

综上，网络流建模与原问题完全等价。Q.E.D.

---

关键洞察

为什么这样建模是最优的？

1. 线性规划视角：

   • 原问题是一个整数线性规划（ILP）
   • 约束矩阵具有全幺模性（网络流的约束矩阵）
   • 因此 LP 松弛的最优解必然是整数解

2. 对偶理论：

   • 最小费用流的对偶问题是最短路
   • SPFA 实际上在求解对偶问题的最优解

3. 贪心性质：

   • 每次增广选择最小费用路径
   • 保证了全局最优性（由凸性保证）

---

关键代码实现

下面给出算法中最关键的代码片段，帮助理解核心思想。

1. 节点编号与空格关联

目标：为每个线索分配唯一节点，并将空格关联到对应的线索。

// 为线索分配节点编号
int node_cnt = 0;
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
        if (op[i][j] & 1) {  // 纵向线索（左下角）
            id[0][i][j] = ++node_cnt;
        }
        if (op[i][j] & 2) {  // 横向线索（右上角）
            id[1][i][j] = ++node_cnt;
        }
    }
}

关键：找到每个空格对应的纵向和横向线索

// 关联空格与线索，统计每个线索对应的空格数
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
        // 处理纵向线索
        if (id[0][i][j]) {
            for (int k = i + 1; k <= n; k++) {
                if (op[k][j] != 4) break;  // 遇到非空格停止
                id0[k][j] = id[0][i][j];   // 空格(k,j)的纵向线索
                v[0][i][j]++;              // 统计线索下方的空格数
            }
        }
        // 横向线索同理...
    }
}

2. 建边核心逻辑

关键思想：用两条边表示绝对值费用函数

对于纵向线索：当前值为 $a$，下方空格数为 $k$，修改代价为 $c$

ll ans = 0;  // 累加初始偏差代价

// 纵向线索建边
if (op[i][j] & 1) {
    ll cost;
    cin >> cost;
    if (cost == -1) cost = INF;  // 不可修改
    
    int clue_val = a[0][i][j];    // 线索值
    int cell_cnt = v[0][i][j];    // 下方空格数
    
    // 计算初始偏差代价
    ans += cost * abs(clue_val - cell_cnt);
    
    // 如果线索值 > 空格数，需要强制减小
    if (clue_val > cell_cnt) {
        add(S, id[0][i][j], clue_val - cell_cnt, -cost);
    }
    
    // 允许增加（弹性边）
    add(S, id[0][i][j], INF, cost);
}

理解：

• 初始时，假设每个空格填 1，纵向线索需要 $k$ 单位流量
• 但实际线索值为 $a$，偏差为 $|a - k|$
• 如果 $a > k$，需要减少 $(a - k)$ 单位流量，费用为 $-c$（回退）
• 然后允许任意增加，费用为 $+c$

3. 空格建边

空格连接纵向线索和横向线索：

// 空格建边
if (op[i][j] & 4) {
    ll cost;
    cin >> cost;
    if (cost == -1) cost = INF;
    
    ll val = b[i][j];          // 空格当前值
    int u = id0[i][j];         // 对应的纵向线索节点
    int v = id1[i][j];         // 对应的横向线索节点
    
    // 计算初始偏差（空格最小值为1）
    ans += cost * abs(val - 1);
    
    // 如果当前值 > 1，需要强制减小
    if (val > 1) {
        add(u, v, val - 1, -cost);
    }
    
    // 允许增加
    add(u, v, INF, cost);
}

4. 可行性检查

核心：检查所有不可修改的数字是否能满足约束

bool check() {
    // 遍历所有边（偶数索引为正向边，奇数为反向边）
    for (int i = 0; i < etot; i += 2) {
        // 检查费用为 INF 的边（对应不可修改的数字）
        if (e[i].co == INF && e[i^1].w > 0) {
            // 正向边费用为 INF，但反向边有剩余容量
            // 说明流量超过了上界，违反了不可修改约束
            return false;
        }
        if (e[i].co == -INF && e[i].w > 0) {
            // 负费用为 INF 的边还有剩余容量
            // 说明强制流没有满流，无法满足下界约束
            return false;
        }
    }
    return true;
}

5. 最小费用流核心：SPFA 寻找增广路

bool bfs(int s, int t) {
    // 初始化距离
    for (int i = 1; i <= tot; i++) {
        dis[i] = INF;
        in[i] = vis[i] = false;
    }
    
    queue<int> q;
    q.push(s);
    dis[s] = 0;
    in[s] = true;
    
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        in[u] = false;
        
        // 遍历所有出边
        for (int i = head[u]; ~i; i = e[i].nxt) {
            int v = e[i].v;
            ll cap = e[i].w, cost = e[i].co;
            
            // 如果有剩余容量且能松弛
            if (cap > 0 && dis[v] > dis[u] + cost) {
                dis[v] = dis[u] + cost;
                if (!in[v]) {
                    q.push(v);
                    in[v] = true;
                }
            }
        }
    }
    
    return dis[t] < INF;  // 是否存在增广路
}

6. DFS 增广

int dfs(int u, int t, int flow) {
    if (u == t || !flow) return flow;
    
    vis[u] = true;
    int pushed = 0;
    
    for (int &i = cur[u]; ~i; i = e[i].nxt) {
        int v = e[i].v;
        ll cap = e[i].w, cost = e[i].co;
        
        // 沿着最短路增广
        if (!vis[v] && cap > 0 && dis[v] == dis[u] + cost) {
            int delta = dfs(v, t, min(flow, cap));
            if (delta) {
                e[i].w -= delta;      // 减少正向边容量
                e[i^1].w += delta;    // 增加反向边容量
                flow -= delta;
                pushed += delta;
                minc += cost * delta; // 累加费用
                
                if (!flow) return pushed;
            }
        }
    }
    
    vis[u] = false;
    return pushed;
}

---

知识点要求

• 1.网络流基础（最大流、最小费用流）
• 2.图论建模
• 3.线性规划思想
• 4.SPFA 最短路算法
• 5.费用函数设计

---

实现要点总结

核心技巧回顾

1. 流量的物理意义

   • 流量 = 数字的最终值（而非修改量）
   • 这样可以直接用流量守恒表示"和"的约束

2. 绝对值函数的线性化

   $$f(x) = c \cdot |x - a| = \begin{cases} c(a-x) + 0 & x \in [0, a] \\ 0 + c(x-a) & x \in [a, +\infty) \end{cases} $$

   用两条边实现：

   • 边1：容量 $(a - \text{lower})$，费用 $-c$（从 $a$ 减到下界）
   • 边2：容量 $\infty$，费用 $+c$（从下界增加）

3. 总代价分解

   $$\text{Total Cost} = \sum_{i} c_i |x_i^{\text{final}} - x_i^{\text{init}}| $$

   分解为：

   $$= \underbrace{\sum_{i} c_i |x_i^{\text{lower}} - x_i^{\text{init}}|}_{\text{初始偏差代价}} + \underbrace{\text{MinCostFlow}}_{\text{网络流优化代价}} $$

4. 不可修改数字的处理

   • 将费用设为 $\pm \infty$
   • 最后检查这些边是否满足流量约束
   • 若不满足则无解

易错点提醒

错误1：将流量理解为修改量

• 错误理解：从 $S$ 流出的流量 = 增加的量
• 正确理解：流经节点的流量 = 数字的最终值

错误2：忘记计算初始偏差代价

• 网络流只计算"从下界到最终值"的代价
• 必须额外加上"从初始值到下界"的代价

错误3：可行性检查不完整

• 不仅要检查是否有流，还要检查不可修改的数字是否被强制修改

代码框架

int main() {
    // 1. 读入数据，建立节点
    // 2. 关联空格与线索
    // 3. 建立网络（双边法处理绝对值）
    ll initial_cost = 0;  // 累加初始偏差
    
    // 4. 求解最小费用流
    ll flow_cost = MinCostFlow::solve(S, T);
    
    // 5. 检查可行性
    if (!check_feasibility()) {
        cout << -1 << endl;
    } else {
        cout << initial_cost + flow_cost << endl;
    }
}

---

拓展思考

变式1：如果允许空格为0怎么办？

修改建边逻辑：

// 原来：空格最小值为1
if (val > 1) add(u, v, val - 1, -cost);
add(u, v, INF, cost);

// 新：空格最小值为0
if (val > 0) add(u, v, val, -cost);
add(u, v, INF, cost);

变式2：如果要求最大化某个目标？

将费用取反，求最大费用流：

// 最小化 → 最大化
add(u, v, cap, -cost);  // 费用取反

变式3：如果有多个可选方案，如何计数？

这就超出了网络流的能力，需要：

• 动态规划（小规模）
• 背包类算法（特殊结构）
• 或者用网络流枚举所有最优解（复杂度高）