深海机器人问题

解题思路

本题要求我们在海底收集价值，有若干个起点和若干个终点，每个起点都会有若干个机器人出发，最终到达终点，每个终点能容纳的机器人数量也是有限的，我们要让尽可能多的机器人走到终点，并且让采集到的总价值最大。（所有价值都在边上，每条边的价值只能收集一次）

本题是一个多源多汇网络流问题，这里常用的技巧就是建立一个虚拟源点和一个虚拟汇点，从虚拟源点向每个起点连一条边，容量是该起点的机器人数量，从每个终点向虚拟汇点连一条边，容量是该终点能容纳的机器人数量。然后每个机器人都可以向上和向右走，所以从每个点向上方点和右方点连一条边。

这样一个流网络就构建出来了，可以发现原问题中每个机器人的行走路径都可以看作流网络中的一条可行流路径，是一一对应的。

我们还需要计算每个方案的具体价值，可以发现所有样本都在边上，因此我们可以将对应边的费用设置成样本的价值，但是本题还要求每条边的样本只能取一次，之后再走到这条边上将不在获得价值。因此我们可以根据两种情况分别连两条边，从每个点向上方点（右方点）连一条容量是 $1$，费用是该边价值的边，再连一条容量是 $+\infty$，费用是 $0$ 的边。这样保证了每条边的价值都只能取一次。

通过以上操作，我们就能将原问题每组方案获得的价值对应到流网络中可行流的费用上。对于所有样本，价值是负的边我们可以不走，而对于价值是正的边，一定是走的越多越好，而只要存在多一条增广路，那么这条增广路就算沿着所有费用是 $0$ 的边走，都一定不会让费用变小，但是流量却会变大，因此在所有最大流中一定存在一个最大流是所有方案中费用最大的，所以原问题的价值最大值就对应到了流网络中的最大费用最大流。

C++ 代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 260, M = 2000, INF = 0x3f3f3f3f;

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

int get(int x, int y) //计算 (x, y) 的唯一编号
{
    return x * (m + 1) + y;
}

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() //判断是否存在最长增广路
{
    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()
{
    int A, B;
    scanf("%d%d%d%d", &A, &B, &n, &m);

    memset(h, -1, sizeof h);

    //所有点的编号为 i = 0 ~ (n + 1) * (m + 1) - 1
    S = (n + 1) * (m + 1), T = S + 1; //源点、汇点

    //建立横向边
    for(int i = 0; i < n + 1; i++)
        for(int j = 0; j < m; j++)
        {
            int x;
            scanf("%d", &x);
            add(get(i, j), get(i, j + 1), 1, x); //从每个点向右边点连边，容量是 1，费用是该边的价值
            add(get(i, j), get(i, j + 1), INF, 0); //从每个点向右边点连边，容量是 INF，费用是 0
        }

    //建立竖向边
    for(int j = 0; j < m + 1; j++)
        for(int i = 0; i < n; i++)
        {
            int x;
            scanf("%d", &x);
            add(get(i, j), get(i + 1, j), 1, x); //从每个点向上边点连边，容量是 1，费用是该边的价值
            add(get(i, j), get(i + 1, j), INF, 0); //从每个点向上边点连边，容量是 INF，费用是 0
        }

    //读入起点
    while(A--)
    {
        int k, x, y;
        scanf("%d%d%d", &k, &x, &y);
        add(S, get(x, y), k, 0); //从源点向每个起点连边，容量是该点机器人数量，费用是 0
    }

    //读入终点
    while(B--)
    {
        int k, x, y;
        scanf("%d%d%d", &k, &x, &y);
        add(get(x, y), T, k, 0); //从每个终点向汇点连边，容量是该点可容纳机器人数量，费用是 0
    }

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

    return 0;
}