很棒的 flow 题,考虑建二分图。
源点向每种零食连边权为 \(a_i\) 的边,每种零食向每个孩子连边权为 \(b_j\) 的边,每个孩子向汇点连边权为 \(c_j\) 的边,这个图的最大流就是答案。
直接跑最大流肯定 T,考虑最大流等价于求这个图的最小割,因此转而求最小割。
发现如果钦定每个零食归源点还是归汇点,那么每个孩子要么断掉所有连向它的归源点的边,要么断掉它连汇点的边。
设归源点的零食个数为 \(x\),每个孩子的最小代价即 \(\min(c_j, b_j \times x)\)。
既然代价只跟 \(x\) 有关了,那我们就枚举 \(x\),零食肯定把最小的 \(n - x\) 个割掉;把所有孩子按照 \(\frac{c_j}{b_j}\) 排序,\(c_j \le b_j \times x\) 的孩子代价就为 \(c_j\),否则为 \(b_j \times x\)。
做完了!太妙了。
code
// Problem: E - Snack
// Contest: AtCoder - AtCoder Regular Contest 125
// URL: https://atcoder.jp/contests/arc125/tasks/arc125_e
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 200100;
ll n, m, a[maxn], c[maxn], d[maxn], e[maxn];
struct node {
ll a, b;
} b[maxn];
inline bool operator < (const node &a, const node &b) {
return a.b * b.a < b.b * a.a;
}
void solve() {
scanf("%lld%lld", &n, &m);
for (int i = 1; i <= n; ++i) {
scanf("%lld", &a[i]);
}
for (int i = 1; i <= m; ++i) {
scanf("%lld", &b[i].a);
}
for (int i = 1; i <= m; ++i) {
scanf("%lld", &b[i].b);
}
sort(a + 1, a + n + 1);
sort(b + 1, b + m + 1);
for (int i = 1; i <= n; ++i) {
c[i] = c[i - 1] + a[i];
}
for (int i = 1; i <= m; ++i) {
d[i] = d[i - 1] + b[i].a;
e[i] = e[i - 1] + b[i].b;
}
ll ans = 1e18;
for (int i = 0; i <= n; ++i) {
int l = 1, r = m, p = 0;
while (l <= r) {
int mid = (l + r) >> 1;
if (b[mid].b <= i * b[mid].a) {
p = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
// printf("%d %d %lld\n", i, p, c[n - i] + e[p] + (d[m] - d[p]) * i);
ans = min(ans, c[n - i] + e[p] + (d[m] - d[p]) * i);
}
printf("%lld\n", ans);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
/*
很棒的 flow 题,考虑建二分图
源点向每种零食连边权为 a_i 的边,每种零食向每个孩子连边权为 b_j 的边,每个孩子向汇点连边权为 c_j 的边
这个图的最大流就是答案
直接跑最大流肯定 T,考虑最大流等价于求这个图的最小割
转而求最小割
发现如果钦定每个零食归 S 还是归 T,那么每个孩子要么断掉所有连向它的归 S 的边,要么断掉它连 T 的边
设归 S 的零食个数为 x,每个孩子的最小代价即 min(c_j, b_j * x)
既然代价只跟 x 有关了,那我们就枚举 x,零食肯定把最小的 n - x 个割掉;
把所有孩子按照 c_j/b_j 排序,c_j >= b_j * x 的孩子代价就为 b_j * x,否则为 c_j
做完了!太妙了
*/
- AtCoder Regular Contest Snack 125atcoder regular contest snack atcoder regular contest 165 minimization atcoder regular contest atcoder regular contest 166 atcoder regular contest degree atcoder regular contest 167 atcoder regular contest sliding atcoder regular contest 164 atcoder regular contest builder subsegments atcoder regular contest