K取方格数问题

解题思路

本题我们需要在一个 $n \times n$ 的矩阵，每个格子上都写着一个非负整数，我们指定 $k$ 条路线，每一步只能往下或往右，每个格子上的数只能取一次，求如何指定这 $k$ 条路线，能让取得的整数和最大。

像这种方格取数问题，存在简单版本，如指定一条路线或两条路线的问题，可以使用线性 dp 来求，但是本题由于最多会有 $10$ 条路径，用 dp 会超时，所以这里考虑用费用流来解决。

首先我们先不去考虑每个格子只能取一次的问题，我们先设法将路线转化成流。起点是左上角，终点是右下角，所有的路线都是从左上角走到右下角。所以我们可以建立一个源点和一个汇点，从源点向左上角连一条容量为 $k$ 的边，从汇点向右下角连一条容量为 $k$ 的边，表示有 $k$ 条路线从左上角走到右下角。然后每个格子都可以向右和向下走，因此从每个格子向右和向下两个格子连边，且每个格子能走多次，没有限制，因此这些边的容量都是 $+\infty$。这样我们就在网格图上建立了一个流网络。

此时可以发现流网络的任意一个可行流和原问题的任意一个方案都是一一对应的。并且原问题的每一个方案都一定有 $k$ 条路线，所以在流网络中对应的可行流一定都是满流。这个比较直观，可以自行证明。

现在回到原题，我们要从所有路线中找出总价值最大的 $k$ 条路线，也就是说我们要在流网络中所有的最大可行流里面找到一个费用最大的方案。那么我们就需要考虑如何将费用结合到流网络里面。

可以发现，本题的所有费用都是在格子上（点上）的，所以我们可以用拆点技巧把每个点拆成入点和出点，然后从每个入点向对应的出点连一条边，费用是该点的价值。

但是这里还有一个限制，就是每个点的价值我们都只能取走一次，以后的若干次再走到这个点上都不会在获得价值。因此我们可以对应这两种情况来建立两条边。对于每个点，从入点向出点连一条容量是 $1$，费用是该点价值的边，再连一条容量是 $+\infty$，费用是 $0$ 的边。这样我们每次走到一个点，只能走一次有费用的边来获取价值，之后的几次都只能走没有费用的边，保证每个点的价值只能取走一次。

这样本题的流网络就构建完成了，并且原问题的任意一组走法都能对应到流网络中的任意一个满流，原问题任意一组走法走过的价值之和都能对应到流网络中任意一个满流的费用。因此我们想求原问题的最大价值，等价于求流网络的最大费用最大流。

C++ 代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 5010, M = 20010, INF = 0x3f3f3f3f;

int n, k, S, T;
int h[N], e[M], f[M], w[M], ne[M], idx; //邻接表
int q[N], d[N], pre[N], incf[N]; //EK 算法的数组
bool st[N]; //spfa 的判重数组

//获取 (x, y) 的编号，t 为 0 表示入点，1 表示出点
int get(int x, int y, int t)
{
    return (x * n + y) * 2 + t;
}

void add(int a, int b, int c, int d) //添加边
{
    e[idx] = b, f[idx] = c, w[idx] = d, ne[idx] = h[a], h[a] = idx++;
    e[idx] = a, f[idx] = 0, w[idx] = -d, ne[idx] = h[b], h[b] = idx++;
}

bool spfa() //spfa 判断是否存在最长增广路
{
    int hh = 0, tt = 1;
    q[0] = S;

    memset(d, -0x3f, sizeof d);
    d[S] = 0;

    memset(incf, 0, sizeof incf);
    incf[S] = INF;

    while(hh != tt)
    {
        int t = q[hh++];
        if(hh == N) hh = 0;
        st[t] = false;

        for(int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if(f[i] && d[j] < d[t] + w[i])
            {
                d[j] = d[t] + w[i];
                pre[j] = i;
                incf[j] = min(incf[t], f[i]);

                if(!st[j])
                {
                    q[tt++] = j;
                    if(tt == N) tt = 0;
                    st[j] = true;
                }
            }
        }
    }

    return incf[T] > 0;
}

int EK() //EK 算法求最大费用最大流
{
    int cost = 0;
    while(spfa())
    {
        int t = incf[T];
        cost += t * d[T];

        for(int i = T; i != S; i = e[pre[i] ^ 1])
        {
            f[pre[i]] -= t;
            f[pre[i] ^ 1] += t;
        }
    }
    return cost;
}

int main()
{
    scanf("%d%d", &n, &k);

    memset(h, -1, sizeof h); //初始化邻接表

    //格子编号为 0 ~ 2 * n * n - 1，入点编号为 2 * n，出点编号为 2 * n + 1
    S = 2 * n * n, T = S + 1; //源点、汇点
    add(S, get(0, 0, 0), k, 0); //从源点向左上角的入点连边，容量是 k，费用是 0
    add(get(n - 1, n - 1, 1), T, k, 0); //从右下角的出点向汇点连边，容量是 k，费用是 0
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
        {
            int x;
            scanf("%d", &x);
            add(get(i, j, 0), get(i, j, 1), 1, x); //从每个点的入点向出点连边，容量是 1，费用是该点的价值
            add(get(i, j, 0), get(i, j, 1), INF, 0); //从每个点的入点向出点连边，容量是 INF，费用是 0
            if(i + 1 < n) add(get(i, j, 1), get(i + 1, j, 0), INF, 0); //从每个点的出点向下方点的入点连边，容量是 INF，费用是 0
            if(j + 1 < n) add(get(i, j, 1), get(i, j + 1, 0), INF, 0); //从每个点的出点向右方点的入点连边，容量是 INF，费用是 0
        }

    printf("%d\n", EK());

    return 0;
}