It's 最小费用流

1. ​​图构建部分​​

// 定义边的结构体，包含目标节点、容量、费用和反向边索引
struct Edge {
    int to, cap, cost, rev;
    Edge(int t, int c, int co, int r) : to(t), cap(c), cost(co), rev(r) {}
};

// 添加边的函数
void add_edge(int from, int to, int cap, int cost) {
    graph[from].emplace_back(to, cap, cost, graph[to].size());
    graph[to].emplace_back(from, 0, -cost, graph[from].size()-1);
}

// 构建图的节点和边
int s = 2 * n * n; // 源点
int t = s + 1;     // 汇点
int node_id = 0;
vector<vector<int>> in_node(n, vector<int>(n));  // 入点编号
vector<vector<int>> out_node(n, vector<int>(n)); // 出点编号

// 为每个格子分配入点和出点编号
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        in_node[i][j] = node_id++;
        out_node[i][j] = node_id++;
    }
}

// 源点连接到起点(0,0)的入点，容量为K，费用为0
add_edge(s, in_node[0][0], K, 0);
// 终点(n-1,n-1)的出点连接到汇点，容量为K，费用为0
add_edge(out_node[n-1][n-1], t, K, 0);

// 为每个格子构建入点到出点的边
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        int cost = -grid[i][j]; // 费用取负数，因为我们需要最大费用
        // 第一次经过该格子时取値，容量为1，费用为格子值的负数
        add_edge(in_node[i][j], out_node[i][j], 1, cost);
        // 后续经过该格子时不取値，容量为K-1，费用为0
        add_edge(in_node[i][j], out_node[i][j], K-1, 0);
        
        // 向下移动的边
        if (i < n-1) {
            add_edge(out_node[i][j], in_node[i+1][j], K, 0);
        }
        // 向右移动的边
        if (j < n-1) {
            add_edge(out_node[i][j], in_node[i][j+1], K, 0);
        }
    }
}

2. ​​最小费用流算法（返回的是负值，输出时注意取负）​​

int min_cost_flow(int s, int t, int f) {
    int res = 0;
    while (f > 0) {
        // 初始化距离数组和队列
        fill(dist, dist + MAXV, INF);
        fill(inque, inque + MAXV, false);
        dist[s] = 0;
        queue<int> que;
        que.push(s);
        inque[s] = true;
        
        // SPFA算法寻找增广路
        while (!que.empty()) {
            int v = que.front(); que.pop();
            inque[v] = false;
            for (int i = 0; i < graph[v].size(); i++) {
                Edge &e = graph[v][i];
                // 如果边有剩余容量且可以松弛
                if (e.cap > 0 && dist[e.to] > dist[v] + e.cost) {
                    dist[e.to] = dist[v] + e.cost;
                    prevv[e.to] = v;       // 记录前驱节点
                    preve[e.to] = i;       // 记录前驱边
                    if (!inque[e.to]) {
                        que.push(e.to);
                        inque[e.to] = true;
                    }
                }
            }
        }
        
        // 如果没有增广路，返回-1
        if (dist[t] == INF) return -1;
        
        // 计算增广路上的最小剩余容量
        int d = f;
        for (int v = t; v != s; v = prevv[v]) {
            d = min(d, graph[prevv[v]][preve[v]].cap);
        }
        f -= d;
        
        // 更新总费用
        res += d * dist[t];
        
        // 更新边的剩余容量
        for (int v = t; v != s; v = prevv[v]) {
            Edge &e = graph[prevv[v]][preve[v]];
            e.cap -= d;
            graph[e.to][e.rev].cap += d;
        }
    }
    return res;
}