JZOJ 4336 Rabbit

考虑对每种胡萝卜和干草建点,从超级源点向第 \(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
#include <cstdio>
#include <algorithm>
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);
}