Tony102's Blog - 模拟最大流
type: channel
link: https://tony102.com/index.php/tag/%E6%A8%A1%E6%8B%9F%E6%9C%80%E5%A4%A7%E6%B5%81/
items: ARC125E Snack

ARC125E Snack
type: item
date: 2021-10-30T11:32:00+08:00
description: LinkSol首先暴力最大流肯定很容易搞出来，跑 $10^4$ 级别应该差不多？考虑模拟最大流，因为最大流可能很大，因此把最大流换成最小割，来考虑割会有什么样的效果。第二列点就代表零食，第三列就是小朋友。现在考虑割，割从源点出发到第二列点的边，对最小割是没有影响的。因为第二列到第三列仍然没有发生改变，贡献给答案的只有 $b_j, c_j$，$a_i$ 总共有多少流出去就行了。假如 $a_i$ 割了 $k$ 条边，那么每次取的就是 $\min {((n-k)b_j, c_j)}$ 。这样就存在一个分界点 $k$，前面的都是 $(n-k)b_j$，后面的全部都选 $c_j$。具体怎么确定选啥，现在是要 $(n-k) b_j > c_j$，只要 $\frac{b_j}{c_j} > \frac{1}{n-k}$ 即 $\frac{c_j}{b_j} > n - k$，先默认 $k=0$。因为分界点每次我们都需要枚举，所以每次取 $\frac{b_j}{c_j} \leq k$ 的位置即可。Code#include <bits/stdc++.h> using namespace std; typedef long long LL; const int SIZE = 2e5 + 5; int n, m; int b[SIZE]; LL s[SIZE], a[SIZE], c[SIZE]; vector < int > flow[SIZE]; namespace GTR { const int bufl = 1 << 15; char buf[bufl], *s = buf, *t = buf; inline int fetch() { if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; } return *s++; } template < class T > inline T read() { T a = 0, b = 1, c = fetch(); while (c < 48 || c > 57) b ^= c == '-', c = fetch(); while (c >= 48 && c <= 57) a = a * 10 + c - 48, c = fetch(); return b ? a : -a; } } using GTR::read; int main() { n = read <int> (), m = read <int> (); LL sumb = 0; for (int i = 1; i <= n; ++ i) a[i] = read <LL> (), s[i] = s[i - 1] + a[i]; for (int i = 1; i <= m; ++ i) b[i] = read <int> (), sumb += b[i]; for (int i = 1; i <= m; ++ i) { c[i] = read <LL> (); LL pos = ceil((double) c[i] / (double) b[i]); if (pos <= n) flow[pos].emplace_back(i); } auto sum = [] (int l, int r) { return s[r] - s[l - 1]; }; sort(a + 1, a + n + 1); LL ans = s[n], s2 = 0, s1 = s[n]; for (int i = 1; i <= n; ++ i) { s1 -= a[n - i + 1]; for (int j: flow[i]) s2 += c[j], sumb -= b[j]; ans = min(ans, s1 + s2 + 1ll * sumb * i); } printf("%lld\n", ans); return 0; }