考虑对每种胡萝卜和干草建点，从超级源点向第 \(i\) 种胡萝卜连容量为 \(m_i\) 的边，从第 \(j\) 种干草向超级汇点连容量为 \(n_j\) 的边，所有 \(M \times N\) 组胡萝卜向干草连容量为 \(1\) 的边。
答案即最大流。
这样显然过不了（
将 \(\{m_i\},\{n_i\}\) 分别升序，设 \(S_m(i) = \sum\limits_{j=1}^i m_j,S_n(i) = \sum\limits_{j=1}^i n_j\)。
根据最大流最小割定理，易知需要最小化 \(S_m(x) + S_n(y) + (M - x)(N - y)\)。
枚举 \(x\)，易知当 \(y\) 为最大的满足 \(n_y \le M - x\) 的 \(y\) 时上式取最小值。
双指针或者在值域意义上维护 \(S_n\) 均可。
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
using namespace std;
const int N = 2.5e6;
int n,m,a[N + 5],ad,b[N + 5],bd;
int c[2][N + 5],cnt;
long long s[2][N + 5],ans = 0x3f3f3f3f3f3f3f3f;
int main()
{
scanf("%d%d%d%d%d%d",&n,&m,a + 1,&ad,b + 1,&bd),++c[0][a[1]],++c[1][b[1]];
for(register int i = 2;i <= n;++i)
a[i] = (58LL * a[i - 1] + ad) % (m + 1),++c[0][a[i]];
for(register int i = 2;i <= m;++i)
b[i] = (58LL * b[i - 1] + bd) % (n + 1),++c[1][b[i]];
for(register int i = 0;i <= m;++i)
for(;c[0][i];--c[0][i],++cnt,s[0][cnt] = s[0][cnt - 1] + i);
for(register int i = 1;i <= n;++i)
s[1][i] = s[1][i - 1] + (long long)c[1][i] * i,c[1][i] += c[1][i - 1];
for(register int i = 0;i <= n;++i)
ans = min(ans,s[0][i] + s[1][n - i] + (long long)(n - i) * (m - c[1][n - i]));
printf("%lld\n",ans);
}