「网络流24题」数字梯形问题-题解

题目传送门: 「Luogu P4013」数字梯形问题

题目大意

梯形的第一行有$m$个数字
从梯形的顶部的$m$个数字开始,在每个数字处可以沿左下或右下方向移动,形成一条从梯形的顶至底的路径。

有三种规则:

1. 从梯形的顶至底的$m$条路径互不相交
2. 从梯形的顶至底的$m$条路径仅在数字结点处相交
3. 从梯形的顶至底的$m$条路径允许在数字结点相交或边相交

求每种规则下经过数字的最大总和

题解

很明显是 最大费用最大流

规则1.

路径不相交,即没有公共点,也就是每个点只能经过一次
将每个点拆成入点和出点,就可以通过控制出入点之间的容量控制经过次数

1. 从 源点 向 第一行的$m$个点的入点 接一条 容量为$1$,费用为$0$ 的边
2. 从 最后一行每个点的出点 接一条 容量为$1$,费用为$0$ 的边
3. 从 每个点的入点 向 每个点的出点 接一条 容量为$1$,费用为该点数字 的边(对答案贡献为该点数字)
4. 从 每个点的出点 向 左下右下两个点的入点 接一条 容量为$1$,费用为$0$ 的边

规则2.

每条路径仅在数字节点相交,也就是不能有重边
无需拆点控制每个点经过的次数,只需给每条向左下右下的边的容量设为$1$,即只能经过一次

1. 从 源点 向 第一行的$m$个点 接一条 容量为$1$,费用为$0$ 的边
2. 从 最后一行每个点 接一条 容量为$inf$,费用为该点数字 的边(每个点可以使用多次)
3. 从 每个点的 向 左下右下两个点 接一条 容量为$1$,费用为该点数字 的边

规则3.

边也可以重合,也就相当于没有规则,可以随意向左下右下走
只需将规则2.中建边3.的容量改成$inf$即可

对于每种情况,求出最大费用最大流,最大费用即为答案
注意求解规则2.3.之前要清空建的图

代码

// 最大费用最大流模板部分省去了
int in[45][45];
int point[45][45], cnt;

int main() {
    m = read(); n = read();
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m + i - 1; ++j) {
            in[i][j] = read();
            point[i][j] = ++cnt;
        }
    }

    // Question 1
    s = 0; t = cnt * 2 + 1;
    for (int i = 1; i <= m; ++i) add(s, point[1][i], 1, 0);
    for (int i = 1; i <= n + m - 1; ++i) add(point[n][i] + cnt, t, 1, 0);
    for (int i = 1; i <= n; ++i) {
        if (i < n) for (int j = 1; j <= m + i - 1; ++j) {
            add(point[i][j] + cnt, point[i + 1][j], 1, 0);
            add(point[i][j] + cnt, point[i + 1][j + 1], 1, 0);
        }
        for (int j = 1; j <= m + i - 1; ++j) 
            add(point[i][j], point[i][j] + cnt, 1, in[i][j]);
    }
    ansflow = MaxCostMaxFlow(anscost);
    printf("%lld\n", anscost);

    // Question 2
    edges.clear();
    for (int i = 0; i < maxn; ++i) G[i].clear();
    s = 0; t = cnt + 1;
    for (int i = 1; i <= m; ++i) add(s, point[1][i], 1, 0);
    for (int i = 1; i <= n + m - 1; ++i) add(point[n][i], t, inf, in[n][i]);
    for (int i = 1; i < n; ++i) for (int j = 1; j <= m + i - 1; ++j) {
        add(point[i][j], point[i + 1][j], 1, in[i][j]);
        add(point[i][j], point[i + 1][j + 1], 1, in[i][j]);
    }
    ansflow = MaxCostMaxFlow(anscost);
    printf("%lld\n", anscost);

    // Question 3
    edges.clear();
    for (int i = 0; i < maxn; ++i) G[i].clear();
    s = 0; t = cnt + 1;
    for (int i = 1; i <= m; ++i) add(s, point[1][i], 1, 0);
    for (int i = 1; i <= n + m - 1; ++i) add(point[n][i], t, inf, in[n][i]);
    for (int i = 1; i < n; ++i) for (int j = 1; j <= m + i - 1; ++j) {
        add(point[i][j], point[i + 1][j], inf, in[i][j]);
        add(point[i][j], point[i + 1][j + 1], inf, in[i][j]);
    }
    ansflow = MaxCostMaxFlow(anscost);
    printf("%lld\n", anscost);

    return 0;
}