数字梯形问题

解题思路

本题给了一个顶部有 $m$ 个点的数字梯形，并且要求我们按照三种规则求出 $m$ 个人从顶部往下走能经过的最大数字总和。

规则一，所有路径的点和边都不能相交，即所有点和所有边都只能走一次
规则二，所有路径的边都不能相交，即所有边只能走一次，所有点可以走无数次
规则三，所有路径的点和边都可以相交，即所有点和所有边都可以走无数次

边只能走一次很好说，只需要将边的容量设置成 $1$ 就行了。点只能走一次就需要用一个常用的拆点技巧，将每个点拆成入点和出点，对每个点的限制就可以对入点到出点之间的边做限制，这里每个点只能走一次，那么就将每个点的入点到出点之间的边的容量设置成 $1$。

然后起点是所有的顶点，终点是所有的底点，因此从源点向所有顶点连一条边，容量是 $1$。从所有底点向汇点连一条边，如果是规则一，那么容量就是 $1$，如果是规则二、三，由于点可以相交，最终可能某一个底点是多条路径的终点，因此这时容量应该设成 $+\infty$。

到此为止这个流网络就构建好了，简单证明一下就可以发现，原问题的任意一个可行方案都和流网络中任意一个可行流是一一对应的，并且由于所有方案都有 $m$ 条路径，而源点出去的流量只有 $m$，因此任意一个可行方案都对应了一个最大流。

然后本题要求的是所有方案中经过点的权值和最大的路径，即权值和最大的一个最大流，我们将每个点的入点到出点的边的费用设置成对应的权值，其余边的费用都设置成 $0$，那么权值和最大的最大流就等价于最大费用最大流，每次根据不同的规则放开点和边的限制重新求一遍最大费用最大流即可。

C++ 代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1200, M = 3800, INF = 0x3f3f3f3f;

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]; //EK 算法需要的数组
bool st[N]; //spfa 算法需要的判重数组
int id[40][40], cost[40][40]; //记录每个点的标号和权值

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()
{
    scanf("%d%d", &m, &n);

    int cnt = 0; //用于记录唯一编号
    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; //给每一个点设置一个唯一编号
            //对于每个点 (i, j)，id[i][j] * 2 表示入点编号，id[i][j] * 2 + 1 表示出点编号
        }

    //规则 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]); //从每个点的入点向出点连一条边，容量是 1，费用是当前点的权值
            if(i == 1) add(S, id[i][j] * 2, 1, 0); //从源点向所有顶点连一条边，容量是 1，费用是 0
            if(i == n) add(id[i][j] * 2 + 1, T, 1, 0); //从所有底点向汇点连一条边，容量是 1，费用是 0
            if(i < n)
            {
                add(id[i][j] * 2 + 1, id[i + 1][j] * 2, 1, 0); //从当前点向正下方的点连一条边，容量是 1，费用是 0
                add(id[i][j] * 2 + 1, id[i + 1][j + 1] * 2, 1, 0); //从当前点向右下方的点连一条边，容量是 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]); //从每个点的入点向出点连一条边，容量是 INF，费用是当前点的权值
            if(i == 1) add(S, id[i][j] * 2, 1, 0); //从源点向所有顶点连一条边，容量是 1，费用是 0
            if(i == n) add(id[i][j] * 2 + 1, T, INF, 0); //从所有底点向汇点连一条边，容量是 INF，费用是 0
            if(i < n)
            {
                add(id[i][j] * 2 + 1, id[i + 1][j] * 2, 1, 0); //从当前点向正下方的点连一条边，容量是 1，费用是 0
                add(id[i][j] * 2 + 1, id[i + 1][j + 1] * 2, 1, 0); //从当前点向右下方的点连一条边，容量是 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]); //从每个点的入点向出点连一条边，容量是 INF，费用是当前点的权值
            if(i == 1) add(S, id[i][j] * 2, 1, 0); //从源点向所有顶点连一条边，容量是 1，费用是 0
            if(i == n) add(id[i][j] * 2 + 1, T, INF, 0); //从所有底点向汇点连一条边，容量是 INF，费用是 0
            if(i < n)
            {
                add(id[i][j] * 2 + 1, id[i + 1][j] * 2, INF, 0); //从当前点向正下方的点连一条边，容量是 INF，费用是 0
                add(id[i][j] * 2 + 1, id[i + 1][j + 1] * 2, INF, 0); //从当前点向右下方的点连一条边，容量是 INF，费用是 0
            }
        }
    printf("%d\n", EK());

    return 0;
}