AcWing 2191. 数字梯形问题    原题链接    困难

作者： 作者的头像   Equation_6 ,  2025-03-24 18:22:56 ·山西 ,  所有人可见 ,  阅读 3

0


题解：数字梯形问题

一、题目分析

本题给定一个由(n)行数字组成的数字梯形，第一行有(m)个数字。需要从梯形顶部的(m)个数字开始，沿着左下或右下方向移动，形成从顶到底的(m)条路径。题目给出三条规则，分别要求(m)条路径互不相交、仅在数字结点处相交、允许在数字结点相交或边相交，要根据这三条规则分别计算出从梯形顶到底的(m)条路径经过的数字总和的最大值。

二、解题思路

本题通过构建网络流模型，利用费用流算法（基于EK算法的费用流实现）来求解不同规则下的最大数字总和。

（一）数据存储与编号

  1. 使用二维数组cost[i][j]存储数字梯形中第(i)行第(j)个位置的数字。
  2. 使用二维数组id[i][j]为数字梯形中的每个位置分配唯一的编号，方便在构建网络流图时使用。
  3. 定义超级源点S和超级汇点T，并通过cnt对节点进行编号管理。

（二）构建网络流图

  1. 节点设置：为数字梯形中的每个位置的数字创建两个节点，例如位置((i, j))对应节点id[i][j] * 2和id[i][j] * 2 + 1，分别表示流入和流出该位置数字的节点。超级源点为S，超级汇点为T。
  2. 边的设置：
    • 对于数字梯形中的每个位置((i, j))，从id[i][j] * 2到id[i][j] * 2 + 1连一条边，容量和费用根据不同规则设置。容量用于限制通过该位置的流量，费用为该位置的数字cost[i][j]，表示经过该位置获得的效益。
    • 当(i = 1)时，从超级源点S到id[i][j] * 2连一条边，容量根据规则设置，费用为(0)，表示从源点开始分配路径。
    • 当(i = n)时，从id[i][j] * 2 + 1到超级汇点T连一条边，容量根据规则设置，费用为(0)，表示路径到达终点。
    • 当(i < n)时，从id[i][j] * 2 + 1到id[i + 1][j] * 2以及id[i + 1][j + 1] * 2连边，容量和费用根据规则设置，用于表示路径的走向。

（三）不同规则下的网络流图构建差异

  1. 规则1（路径互不相交）：
    • 从id[i][j] * 2到id[i][j] * 2 + 1的边容量设为(1)，表示每个位置最多只能被一条路径经过。
    • 从源点到起点的边容量为(1)，从终点到汇点的边容量为(1)，中间连接上下层节点的边容量也为(1)，以此保证路径不相交。
  2. 规则2（仅在数字结点处相交）：
    • 从id[i][j] * 2到id[i][j] * 2 + 1的边容量设为无穷大INF，表示该位置可以被多条路径经过。
    • 从源点到起点的边容量为(1)，限制从源点出发的路径数量；从终点到汇点的边容量为无穷大INF，因为终点处可以汇聚多条路径。中间连接上下层节点的边容量为(1)，确保在边上不相交。
  3. 规则3（允许在数字结点相交或边相交）：
    • 从id[i][j] * 2到id[i][j] * 2 + 1的边容量设为无穷大INF。
    • 从源点到起点的边容量为(1)，从终点到汇点的边容量为无穷大INF，中间连接上下层节点的边容量也设为无穷大INF，即完全不限制路径在节点和边上的相交情况。

（四）费用流算法求解

  1. 添加边函数add：用于在邻接表中添加边及其反向边，设置正向边和反向边的终点、容量和费用，方便在增广路径时处理流量的退还和费用的计算。
  2. 寻找增广路径（spfa函数）：使用spfa算法寻找费用最大的增广路径（因为要使数字总和最大）。初始化距离数组d为负无穷大（与常规求最小费用时初始化为正无穷大相反），最小剩余容量数组incf为(0)，将源点加入队列并设置相关初始值。在队列不为空时，遍历节点的邻接边，更新邻接点的距离、前驱边和最小剩余容量，若邻接点不在队列中则加入队列。当队列为空时，根据汇点的最小剩余容量判断是否找到增广路径。
  3. 更新流量与费用（EK函数）：当找到增广路径后，获取汇点的最小剩余容量(t)，更新总费用（累加(t * d[T])），并沿着增广路径更新边的容量（正向边减去(t)，反向边加上(t)）。不断重复寻找增广路径和更新的过程，直到不存在增广路径，返回的总费用即为该规则下的最大数字总和。

（五）main函数流程

  1. 读取数字梯形的行数n和第一行的数字个数m，并为超级源点S和超级汇点T编号。
  2. 读取数字梯形的所有数字，并为每个位置编号。
  3. 按照规则1构建网络流图，调用EK函数计算并输出最大数字总和。
  4. 按照规则2构建网络流图（重新初始化邻接表），调用EK函数计算并输出最大数字总和。
  5. 按照规则3构建网络流图（再次重新初始化邻接表），调用EK函数计算并输出最大数字总和。

三、代码实现细节

（一）头文件与全局变量

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1200, M = 4000, INF = 1e8;

int m, n, S, T;
int h[N], e[M], f[M], w[M], ne[M], idx;
int q[N], d[N], pre[N], incf[N];
bool st[N];
int id[40][40], cost[40][40];
  • 引入输入输出、字符串操作和算法相关头文件，并使用标准命名空间。
  • 定义常量N表示节点最大数量，M表示边的最大数量，INF表示无穷大。
  • 定义变量m、n分别表示数字梯形第一行的数字个数和行数，S、T表示超级源点和超级汇点。
  • 定义数组h[N]为邻接表头数组，e[M]存储边的终点，f[M]存储边的容量，w[M]存储边的费用，ne[M]存储同一起点下一条边的编号，idx用于记录边的编号。
  • 定义数组q[N]为spfa算法的队列，d[N]记录从源点到各点的距离，pre[N]记录前驱边，incf[N]记录从源点到各点的最小剩余容量。
  • 定义布尔数组st[N]用于标记节点是否在队列中。
  • 定义二维数组id[40][40]为数字梯形每个位置编号，cost[40][40]存储数字梯形的数字。

（二）添加边函数add

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 ++ ;
}

该函数用于添加边及其反向边，设置正向边和反向边的相关参数。

（三）spfa函数

bool spfa()
{
    int hh = 0, tt = 1;
    memset(d, -0x3f, sizeof d);
    memset(incf, 0, sizeof incf);
    q[0] = S, d[S] = 0, incf[S] = INF;
    while (hh != tt)
    {
        int t = q[hh ++ ];
        if (hh == N) hh = 0;
        st[t] = false;

        for (int i = h[t]; ~i; i = ne[i])
        {
            int ver = e[i];
            if (f[i] && d[ver] < d[t] + w[i])
            {
                d[ver] = d[t] + w[i];
                pre[ver] = i;
                incf[ver] = min(f[i], incf[t]);
                if (!st[ver])
                {
                    q[tt ++ ] = ver;
                    if (tt == N) tt = 0;
                    st[ver] = true;
                }
            }
        }
    }
    return incf[T] > 0;
}
  • 初始化队列头指针hh = 0，尾指针tt = 1，距离数组d为负无穷大，最小剩余容量数组incf为(0)。将源点加入队列并设置初始值。
  • 当队列不为空时，取出队头节点(t)，标记该节点不在队列中。遍历节点(t)的邻接边，更新邻接点信息，若邻接点不在队列中则加入队列。
  • 根据汇点的最小剩余容量判断是否找到增广路径。

（四）EK函数

int 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;
}
  • 初始化总费用cost为(0)。
  • 当存在增广路径时，获取汇点的最小剩余容量(t)，更新总费用并沿着增广路径更新边的容量。
  • 当不存在增广路径时，返回总费用。

（五）main函数

int main()
{
    int cnt = 0;
    scanf("%d%d", &m, &n);
    S = ++ cnt;
    T = ++ cnt;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m + i - 1; j ++ )
        {
            scanf("%d", &cost[i][j]);
            id[i][j] = ++ cnt;
        }

    // 规则1
    memset(h, -1, sizeof h), idx = 0;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m + i - 1; j ++ )
        {
            add(id[i][j] * 2, id[i][j] * 2 + 1, 1, cost[i][j]);
            if (i == 1) add(S, id[i][j] * 2, 1, 0);
            if (i == n) add(id[i][j] * 2 + 1, T, 1, 0);
            if (i < n)
            {
                add(id[i][j] * 2 + 1, id[i + 1][j] * 2, 1, 0);
                add(id[i][j] * 2 + 1, id[i + 1][j + 1] * 2, 1, 0);
            }
        }
    printf("%d\n", EK());

    // 规则2
    memset(h, -1, sizeof h), idx = 0;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m + i - 1; j ++ )
        {
            add(id[i][j] * 2, id[i][j] * 2 + 1, INF, cost[i][j]);
            if (i == 1) add(S, id[i][j] * 2, 1, 0);
            if (i == n) add(id[i][j] * 2 + 1, T, INF, 0);
            if (i < n)
            {
                add(id[i][j] * 2 + 1, id[i + 1][j] * 2, 1, 0);
                add(id[i][j] * 2 + 1, id[i + 1][j + 1] * 2, 1, 0);
            }
        }
    printf("%d\n", EK());

    // 规则3
    memset(h, -1, sizeof h), idx = 0;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m + i - 1; j ++ )
        {
            add(id[i][j] * 2, id[i][j] * 2 + 1, INF, cost[i][j]);
            if (i == 1) add(S, id[i][j] * 2, 1, 0);
            if (i == n) add(id[i][j] * 2 + 1, T, INF, 0);
            if (i < n)
            {
                add(id[i][j] * 2 + 1, id[i + 1][j] * 2, INF, 0);
                add(id[i][j] * 2 + 1, id[i + 1][j + 1] * 2, INF, 0);
            }
        }
    printf("%d\n", EK());

    return 0;
}
  • 读取数字梯形的相关参数，为源点、汇点和数字梯形的位置编号。
  • 按照规则1构建网络流图，调用EK函数输出结果。
  • 重新初始化邻接表，按照规则2构建网络流图，调用EK函数输出结果。
  • 再次重新初始化邻接表，按照规则3构建网络流图，调用EK函数输出结果。

四、时间复杂度和空间复杂度

（一）时间复杂度

  • 建图阶段：对于每个规则，构建网络流图的时间复杂度为(O(n \times (m + n)))，因为需要遍历数字梯形的每个位置来添加边。
  • 费用流算法阶段：每次spfa寻找增广路径的时间复杂度在最坏情况下为(O(N))（(N)为节点数），而基于spfa的费用流算法最多执行(O(M))次增广（(M)为边数）。所以每个规则下费用流算法的时间复杂度为(O(N \times M))。由于有(3)个规则，总的时间复杂度为(O(3 \times N \times M + 3 \times n \times (m + n)))。在本题数据范围内(n, m \leq 20)，实际运行效率相对较好。

（二）空间复杂度

主要空间消耗在存储图的邻接表以及辅助数组上。邻接表的空间复杂度为(O(M))，辅助数组（如队列、距离数组、前驱数组等）的空间复杂度为(O(N))。此外，还需要存储数字梯形的数字和编号，空间复杂度为(O(n \times (m + n)))。所以总的空间复杂度为(O(M + N + n \times (m + n)))。

0 评论

1024
x