方格取数加强版

题目解析

这道题目是**最大费用最大流（Max Cost Maximum Flow）**在网格路径规划中的经典应用。它是“方格取数”普通版（通常 $K=2$ ）的泛化形式。当 $K$ 增大到 $10$ 时，传统的 DP 状态维度会爆炸，而网络流则能优雅地处理“路径重叠”与“收益递减”的问题。

🧠 离散数学：本质理解

1. 算子映射：从“取数”到“容量限制”

题目核心冲突在于：同一个格子的数值只能取一次，但可以经过多次。

这在离散结构中对应一种“非线性收益”：

第 1 次进入：贡献 $A_{i,j}$ ，消耗 1 单位流量。
第 2 到 $K$ 次进入：贡献 $0$ ，消耗剩余流量。

我们通过**拆点（Node Splitting）**将一个格子的物理位置转化为两个逻辑节点：入点 $U$ 和出点 $V$ 。

2. 数学推导：流量平衡与代价函数

设每条路径为流网络中的一条增广路。

总流量 $K$ ：限制了我们最多走 $K$ 次。
边的构造：

对于每个格子 $(i,j)$ ，建立边 $Edge(U_{i,j}, V_{i,j})$ ：
- 边 A：容量 $1$ ，费用 $A_{i,j}$ （代表第一次经过，取走数值）。
- 边 B：容量 $K-1$ ，费用 $0$ （代表后续经过，不产生收益）。

这种构造巧妙地利用了费用流的贪心属性：算法会优先跑费用最高的边（即先取走数值），然后再跑费用为 0 的边。

🛠️ 网络流建模

节点设计

源点 $S$ ，汇点 $T$ 。
点集：每个格子 $(i,j)$ 拆为 $In(i,j)$ 和 $Out(i,j)$ 。

连边逻辑

$S \to In(1,1)$ ：容量 $K$ ，费用 $0$ 。
$Out(n,n) \to T$ ：容量 $K$ ，费用 $0$ 。
格子内部（拆点边）：
- $In(i,j) \to Out(i,j)$ ，容量 $1$ ，费用 $A_{i,j}$ 。
- $In(i,j) \to Out(i,j)$ ，容量 $K-1$ ，费用 $0$ 。
格子外部（移动边）：
- $Out(i,j) \to In(i,j+1)$ （右移），容量 $K$ ，费用 $0$ 。
- $Out(i,j) \to In(i+1,j)$ （下移），容量 $K$ ，费用 $0$ 。

注意：本题求的是最大费用。在使用你提供的 MCMF 模板（基于最小费用）时，只需将费用 $A_{i,j}$ 取负，最后结果再取负即可。

📶 信号反射 & 思维模板

关键信号 (Key Signals)：
- “走 $K$ 次”：限制总流量为 $K$ 。
- “取走后变 0”：典型的非线性收益，通过拆点+多重边（容量 1 费用 $V$ ，容量 $K-1$ 费用 $0$ ）解决。
- “网格结构 + 只能向右向下”：暗示了图是一个有向无环图（DAG），但在 $K$ 次路径重叠时，网络流比 DP 更具普适性。
逻辑跃迁 (Logic Jump)：

从“寻找 $K$ 条路径”跃迁到“在一个残余网络中推送 $K$ 单位流量”。关键转折点在于：如何用边的容量和费用来描述格子的状态变化。
模式识别 (Pattern Recognition)：

以后看到 “资源有限（ $K$ 次）+ 收益随采集次数递减（或仅限一次）”，本能反应就应该是 “拆点费用流，第一条边放收益，后续边放零或惩罚”。

代码

cpp

/**
 * Author by Rainboy blog: https://blog.roj.ac.cn
 */

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

// 使用你模板中的常量，确保空间充足
const int maxn = 1e5 + 5; 
const int maxe = 1e6 + 5; 
const int INF_INT = 0x3f3f3f3f;

struct linkList {
    typedef struct {int u,v,w,c,next;} edge; 
    edge e[maxe];
    int h[maxn], edge_cnt = 0;
    linkList() { reset(); }
    void reset() {
        edge_cnt = 0;
        memset(h, -1, sizeof(h));
    }
    void add(int u, int v, int w = 0, int c = 0) {
        e[edge_cnt] = {u, v, w, c, h[u]};
        h[u] = edge_cnt++;
    }
    edge& operator[](int i) { return e[i]; }
} e;

struct MCMF {
    int dis[maxn], flow[maxn], pre[maxn], last[maxn];
    bool vis[maxn];
    int n;
    long long max_flow, min_cost;

    void init(int n) {
        e.reset();
        this->n = n;
    }

    void addEdge(int u, int v, int cap, int cost) {
        e.add(u, v, cap, cost);      
        e.add(v, u, 0, -cost);       
    }

    bool spfa(int s, int t) {
        for(int i = 0; i <= n + 1; i++) dis[i] = INF_INT, vis[i] = 0, flow[i] = INF_INT;
        queue<int> q;
        dis[s] = 0; vis[s] = 1; pre[t] = -1;
        q.push(s);
        
        while (!q.empty()) {
            int u = q.front(); q.pop();
            vis[u] = 0;
            for(int i = e.h[u]; ~i; i = e[i].next) {
                int v = e[i].v;
                if (e[i].w > 0 && dis[v] > dis[u] + e[i].c) {
                    dis[v] = dis[u] + e[i].c;
                    pre[v] = u;
                    last[v] = i;
                    flow[v] = min(flow[u], e[i].w);
                    if (!vis[v]) {
                        vis[v] = 1;
                        q.push(v);
                    }
                }
            }
        }
        return pre[t] != -1;
    }

    void solve(int s, int t) {
        max_flow = 0; min_cost = 0;
        while (spfa(s, t)) {
            int f = flow[t];
            max_flow += f;
            min_cost += (long long)f * dis[t];
            int now = t;
            // 修正：严格按照路径回溯更新残余网络
            while (now != s) {
                int edge_idx = last[now];
                e[edge_idx].w -= f;
                e[edge_idx ^ 1].w += f;
                now = pre[now];
            }
        }
    }
} mcmf;

// 坐标转换逻辑：入点为 id，出点为 id + n*n
int get_id(int r, int c, int n, bool out) {
    int id = (r - 1) * n + c;
    return out ? id + n * n : id;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, k;
    if (!(cin >> n >> k)) return 0;

    int S = 0, T = 2 * n * n + 1;
    mcmf.init(T);

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            int val; cin >> val;
            int in_node = get_id(i, j, n, false);
            int out_node = get_id(i, j, n, true);

            // 1. 格子内部拆点连边：第一趟有收益，后续无收益
            mcmf.addEdge(in_node, out_node, 1, -val);
            mcmf.addEdge(in_node, out_node, k, 0); // 容量给 k 确保后续路径可通行

            // 2. 只有 Out 点才能向下一个 In 点移动
            if (j + 1 <= n) 
                mcmf.addEdge(out_node, get_id(i, j + 1, n, false), k, 0);
            if (i + 1 <= n) 
                mcmf.addEdge(out_node, get_id(i + 1, j, n, false), k, 0);
        }
    }

    // 源点进 (1,1)，(n,n) 出到汇点
    mcmf.addEdge(S, get_id(1, 1, n, false), k, 0);
    mcmf.addEdge(get_id(n, n, n, true), T, k, 0);

    mcmf.solve(S, T);
    cout << -mcmf.min_cost << endl;

    return 0;
}

目录