题目描述

MF 城建立在一片高原上。由于城市唯一的水源是位于河谷地带的湖中，人们在坡地上修筑了一片网格状的抽水水管，以将湖水抽入城市。这片管网由 n行m列节点（红色，图中n=5，m=6），横向管道（紫色）和纵向管道（橙色）构成。行和列分别用 1到 n 的整数和 1 到 m的整数表示。第1行的任何一个节点均可以抽取湖水，湖水到达第n行的任何一个节点即算作引入了城市。除第一行和最后一行外，横向相邻或纵向相邻的两个节点之间一定有一段管道，每一段管道都有各自的最大的抽水速率，并需要根据情况选择抽水还是放水。对于纵向的管道（橙色），允许从上方向下方抽水或从下方向上方放水；如果从图中的上方向下方抽水，那么单位时间内能通过的水量不能超过管道的最大速率；如果从下方向上方放水，因为下方海拔较高，因此可以允许有任意大的水量。对于横向的管道（紫色），允许从左向右或从右向左抽水，不允许放水，两种情况下单位时间流过的水量都不能超过管道的最大速率。
现在 MF 城市的水务负责人想知道，在已知每个管道单位时间容量的情况下，MF 城每单位时间最多可以引入多少的湖水。

样例

输入格式
由于输入规模较大，我们采用伪随机生成的方式生成数据。
每组数据仅一行包含 6个非负整数 n,m,A,B,Q,X0。其中，n 和 m 如前文所述，表示管网的大小，保证 2≤n,m≤5000；保证 1≤A,B,Q,X0≤10^9。A,B,Q,X0是数据生成的参数，我们用如下的方式定义一个数列 {Xi}：Xi+1=(AXi+B)modQ,(i≥0)
我们将数列的第 1项到第 (n−1)m 项作为纵向管道的单位时间容量，其中 X(s−1)m+t 表示第 s 行第 t 列的节点到第 s+1 行第 t 列管道单位时间的容量；将数列的第(n−1)m+1项到第(n−1)m+(n−2)(m−1)项（即接下来的(n−2)(m−1)项）作为横向管道的单位时间容量，其中 X(n−1)m+(s−2)(m−1)+t 表示第 s 行第 t 列的节点到第 s 行第 t+1列管道单位时间的容量。

输出格式
输出一行一个整数，表示 MF 城每单位时间可以引入的水量。

注意计算过程中有些参数可能超过 32位整型表示的最大值，请注意使用 64位整型存储相应数据。

输入样例1：
3 3 10 3 19 7

输出样例1：
38

算法1

不用最大流，请看注释
正确性证明不是很好理解

C++ 代码

#include <bits/stdc++.h>
using namespace std;

const int N = 5050;
int n, m, A, B, Q, X;
int row[N][N], col[N][N]; //row:横向，col：纵向
long long d[N]; //d:drain, d[i]:第i行的排水能力

int main(){
    cin>>n>>m>>A>>B>>Q>>X;
    for (int i = 1; i <= n - 1; i ++ )
        for (int j = 1; j <= m; j ++ )
            col[i][j] = X = (1ll * A * X + B) % Q;
    for (int i = 2; i <= n; i ++ )
        for (int j = 1; j < m; j ++ )
            row[i][j] = X = (1ll * A * X + B) % Q;

    for (int j = 1; j <= m; j ++ )  {  //一列一列计算
        for (int i = 1; i <= n - 1; i ++ )
            d[i] += col[i][j];  //每一行纵向输送相加，但可能达不到，后面调整
        for (int i = 2; i <= n - 1; i ++ )
            d[i] = min(d[i], d[i - 1] + row[i][j]);  //上方输送能力决定下方的下限
        for (int i = n - 2; i; i -- )
            d[i] = min(d[i], d[i + 1] + row[i + 1][j]); //下方排放能力决定上方的下限
            //假设右边可以自由进出左边，只是限制为横线容量row
            //这个前提是右边纵向输送能力完全满足要求，但最后一列，row全部为0
            //这样就满足这个要求
    }
    //最后调整完成后，所有d[i]都相同
    printf("%lld\n", d[1]);
    return 0;
}