题解：深海机器人问题

一、题目分析

本题描述了深海资源考察探险队的场景，潜艇到达深海海底后，多个深海机器人从各自出发位置沿着向北或向东的方向移动，目标是在尽可能多机器人到达目的地的前提下，采集到价值最高的生物标本。生物标本由最先遇到的机器人采集且只能采集一次。题目给定机器人的出发和目标位置，以及网格边上生物标本的价值，要求计算最优移动方案下采集到的生物标本的最高总价值。

二、解题思路

本题通过构建网络流模型，利用费用流算法（基于EK算法的费用流实现）来求解最高总价值。

（一）节点编号与映射

定义get函数，将二维网格中的坐标((x, y))映射为唯一的节点编号。通过x * (m + 1) + y的方式，方便后续构建网络流图时对节点进行操作。

（二）构建网络流图

1. 节点设置：定义超级源点S和超级汇点T。源点编号为(n + 1) * (m + 1)，汇点编号为S + 1。
2. 边的设置：
   • 水平方向的边：对于每一行，从坐标((i, j))到((i, j + 1))连两条边。一条边容量为1，费用为该水平网格边上生物标本的价值c，表示该标本只能被采集一次；另一条边容量为无穷大INF，费用为0，用于处理路径经过但标本已被采集的情况。
   • 垂直方向的边：对于每一列，从坐标((j, i))到((j + 1, i))连两条边。同样，一条边容量为1，费用为该垂直网格边上生物标本的价值c；另一条边容量为无穷大INF，费用为0。
   • 源点与出发位置的边：根据每个深海机器人的出发位置((x, y))和数量k，从超级源点S到出发位置对应的节点get(x, y)连一条边，容量为k，费用为0，表示源点可以发出对应数量的机器人到该位置。
   • 目标位置与汇点的边：根据每个深海机器人的目标位置((x, y))和数量r，从目标位置对应的节点get(x, y)到超级汇点T连一条边，容量为r，费用为0，表示对应数量的机器人可以从该位置到达汇点。

（三）费用流算法求解

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

（四）main函数流程

1. 读取网格的维度信息n、m，以及机器人出发位置数量A和目标位置数量B。设置超级源点S和超级汇点T的编号，并初始化邻接表。
2. 读取水平方向网格边上生物标本的价值，并在相应节点间连边。
3. 读取垂直方向网格边上生物标本的价值，并在相应节点间连边。
4. 根据每个深海机器人的出发位置和数量，在源点与出发位置节点间连边。
5. 根据每个深海机器人的目标位置和数量，在目标位置节点与汇点间连边。
6. 调用EK函数计算并输出采集到的生物标本的最高总价值。

三、代码实现细节

（一）头文件与全局变量

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

using namespace std;

const int N = 260, M = 2000, INF = 1e8;

int n, m, 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];

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

（二）节点编号函数get

int get(int x, int y)
{
    return x * (m + 1) + y;
}

该函数根据网格坐标((x, y))计算出唯一的节点编号，方便后续构建网络流图。

（三）添加边函数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 A, B;
    scanf("%d%d%d%d", &A, &B, &n, &m);
    S = (n + 1) * (m + 1), T = S + 1;
    memset(h, -1, sizeof h);
    for (int i = 0; i <= n; i ++ )
        for (int j = 0; j < m; j ++ )
        {
            int c;
            scanf("%d", &c);
            add(get(i, j), get(i, j + 1), 1, c);
            add(get(i, j), get(i, j + 1), INF, 0);
        }
    for (int i = 0; i <= m; i ++ )
        for (int j = 0; j < n; j ++ )
        {
            int c;
            scanf("%d", &c);
            add(get(j, i), get(j + 1, i), 1, c);
            add(get(j, i), get(j + 1, i), INF, 0);
        }
    while (A -- )
    {
        int k, x, y;
        scanf("%d%d%d", &k, &x, &y);
        add(S, get(x, y), k, 0);
    }
    while (B -- )
    {
        int r, x, y;
        scanf("%d%d%d", &r, &x, &y);
        add(get(x, y), T, r, 0);
    }

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

    return 0;
}

• 读取相关参数，设置源点和汇点编号，初始化邻接表。
• 读取水平和垂直方向网格边上生物标本的价值，并构建相应的边。
• 根据机器人的出发和目标位置信息，构建源点与出发位置、目标位置与汇点之间的边。
• 调用EK函数输出采集到的生物标本的最高总价值。

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

（一）时间复杂度

• 建图阶段：构建网络流图需要遍历水平和垂直方向的网格边，以及处理机器人的出发和目标位置，时间复杂度为(O((n + m) \times (n + m) + A + B))。
• 费用流算法阶段：每次spfa寻找增广路径的时间复杂度在最坏情况下为(O(N))，而基于spfa的费用流算法最多执行(O(M))次增广（(M)为边数）。边数(M)与(n)、(m)相关，约为(O((n + m)^2))，所以费用流算法的时间复杂度为(O(N \times M)=O((n + m)^2 \times (n + m)) = O((n + m)^3))。因此，总的时间复杂度为(O((n + m)^3))。

（二）空间复杂度

主要空间消耗在存储图的邻接表以及辅助数组上。邻接表的空间复杂度为(O(M)=O((n + m)^2))，辅助数组（如队列、距离数组、前驱数组等）的空间复杂度为(O(N))。所以总的空间复杂度为(O((n + m)^2))。