Link

Sol

首先暴力最大流肯定很容易搞出来,跑 $10^4$ 级别应该差不多?

考虑模拟最大流,因为最大流可能很大,因此把最大流换成最小割,来考虑割会有什么样的效果。

5xPRwq.png

第二列点就代表零食,第三列就是小朋友。

现在考虑割,割从源点出发到第二列点的边,对最小割是没有影响的。因为第二列到第三列仍然没有发生改变,贡献给答案的只有 $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;
}
最后修改:2021 年 10 月 30 日
如果觉得我的文章对你有用,请随意赞赏