\(\mathcal{Description}\)
??Link.
??把 \(n\) 种零食分给 \(m\) 个人,第 \(i\) 种零食有 \(a_i\) 个;第 \(i\) 个人得到同种零食数量不超过 \(b_i\),总数量不超过 \(c_i\),求最多分出的零食数量。
??\(n,m\le2\times10^5\)。
\(\mathcal{Solution}\)
??很容易看出这是网络流模型:
- 源点 \(S\) 连向每种零食 \(i\),容量 \(a_i\);
- 零食 \(i\) 连向人 \(j\),容量 \(b_j\);
- 人 \(j\) 连向汇点 \(T\),容量 \(c_j\)。
??答案即为 \(S\) 到 \(T\) 的最大流。
??在这样的网络中,我们发现容量的种类数少,而边数很多,可以推出边的容量与这条边具体连接两端结点的相关性不强。这种时候,可以尝试手算最小割。
??具体地,设零食集合 \(A\) 被割入 \(S\) 部,那么对于一个人 \(i\),他被割入 \(S\) 部的代价为 \(c_i\),被割入 \(T\) 部的代价是 \(|A|b_i\),我们应取两者较小值,而这果然与 \(A\) 集合具体构成不相关。所以,枚举 \(|A|\in[0,n]\),每个人一定在一段前缀中被割入 \(T\) 部,在其余情况被割入 \(S\) 部,利用单调性维护这一过程,做到复杂度 \(\mathcal O(n\log n+m\log m)\),两个瓶颈皆为排序。
\(\mathcal{Code}\)
/*~Rainybunny~*/
#include <bits/stdc++.h>
#define rep( i, l, r ) for ( int i = l, rep##i = r; i <= rep##i; ++i )
#define per( i, r, l ) for ( int i = r, per##i = l; i >= per##i; --i )
typedef long long LL;
inline void chkmin( LL& a, const LL b ) { b < a && ( a = b ); }
const int MAXN = 2e5;
int n, m, b[MAXN + 5], ord[MAXN + 5];
LL a[MAXN + 5], c[MAXN + 5];
int main() {
scanf( "%d %d", &n, &m );
rep ( i, 1, n ) scanf( "%lld", &a[i] );
rep ( i, 1, m ) scanf( "%d", &b[i] ), ord[i] = i;
rep ( i, 1, m ) scanf( "%lld", &c[i] );
std::sort( a + 1, a + n + 1,
[]( const LL u, const LL v ) { return u > v; } );
std::sort( ord + 1, ord + m + 1, []( const int u, const int v )
{ return 1ull * c[u] * b[v] < 1ull * c[v] * b[u]; } );
LL sa = 0, sb = 0, sc = 0, ans = 1ll << 60;
rep ( i, 1, n ) sa += a[i];
rep ( i, 1, m ) sb += b[i];
for ( int i = 0, j = 1; i <= n; ++i ) {
sa -= a[i];
for ( ; j <= m && 1ll * i * b[ord[j]] > c[ord[j]];
sb -= b[ord[j]], sc += c[ord[j++]] );
chkmin( ans, sa + i * sb + sc );
}
printf( "%lld\n", ans );
return 0;
}