省队集训 Day3 陈姚班

【题目大意】

给一张网格图，上往下有流量限制，下往上没有，左往右有流量限制。

$n * m \leq 2.5 * 10^6$

【题解】

考场直接上最大流，50分。竟然傻逼没看出狼抓兔子。

平面图转对偶图，其中没有流量限制（inf）不用转，然后直接在DAG上分层dp即可。

复杂度$O(nm)$，但是这样过不去被卡常了。

出题人的做法是先处理出每层初始的那个随机数，然后每层往下直接做，这样因为是一维数组，所以寻址方便，不会被卡常。

我的做法是动态开数组（用new），然后比较两维大小来分配第一维给谁，第一维优先分配给小的，第二维给大的。

然后如果n >= m可以用指针优化，所以阈值设为n * 10 >= m即可（虽然没啥必要）

# include <stdio.h>

# include <string.h>

# include <iostream>

# include <algorithm>

// # include <bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef long double ld;

typedef unsigned long long ull;

const int M = 2.5e5 + ;

const int mod = 1e9+;

namespace irand {

    int A, B, Q, X0;

    inline void getseed() {

        cin >> A >> B >> Q >> X0;

    }

    inline int getint() {

        return X0 = (1ll * A * X0 + B) % Q;

    }

}

int n, m, **ad, **bd;

ll f[M];

int main() {

    cin >> n >> m; irand :: getseed();

    if(n *  >= m) {

        ad = new int*[m + ]; bd = new int*[m + ]; --n;

        for (register int i=; i<=m; ++i) ad[i] = new int[n + ], bd[i] = new int[n + ];

        for (register int i=; i<=n; ++i)

            for (register int j=; j<=m; ++j)

                ad[j][i] = irand :: getint();

        for (register int i=; i<n; ++i)

            for (register int j=; j<m; ++j)

                bd[j][i] = irand :: getint();

        for (register int i=; i<m; ++i) {

            register int *A = ad[i], *B = bd[i];

            for (register int j=; j<=n; ++j) f[j] += A[j];

            for (register int j=; j<=n; ++j) f[j] = min(f[j], f[j-]+B[j-]);

            for (register int j=n-; j; --j) f[j] = min(f[j], f[j+]+B[j]);

        }

        ll ans = 1e18;

        for (int i=; i<=n; ++i) f[i] += ad[m][i];

        for (int i=; i<=n; ++i) ans = min(ans, f[i]);

        cout << ans << endl;

        return ;

    } else {

        ad = new int*[n + ]; bd = new int*[n + ]; --n;

        for (register int i=; i<=n; ++i) ad[i] = new int[m + ], bd[i] = new int[m + ];

        for (register int i=; i<=n; ++i)

            for (register int j=; j<=m; ++j)

                ad[i][j] = irand :: getint();

        for (register int i=; i<n; ++i)

            for (register int j=; j<m; ++j)

                bd[i][j] = irand :: getint();

        for (register int i=; i<m; ++i) {

            for (register int j=; j<=n; ++j) f[j] += ad[j][i];

            for (register int j=; j<=n; ++j) f[j] = min(f[j], f[j-]+bd[j-][i]);

            for (register int j=n-; j; --j) f[j] = min(f[j], f[j+]+bd[j][i]);

        }

        ll ans = 1e18;

        for (int i=; i<=n; ++i) f[i] += ad[i][m];

        for (int i=; i<=n; ++i) ans = min(ans, f[i]);

        cout << ans << endl;

        return ;

    }

}