题解：P13847 [CERC 2023] Cakes

j23wuyifan · 2025-09-04 14:43:45 · 题解

思路：

因为原料会消耗，所以直接减去即可。

我们发现不太好统计最大收益，正难则反，我们可以考虑计算需减去的最小代价，及求最小割。

接下来考虑建图，有和 P11879 类似的思路，将源点向工具连一条 t[i] 的边，表示该工具的花费，对于 i 所需要的工具 j，连一条从 j 到 i 边权为正无穷的边，表示这条边不能拆，最后每个蛋糕向汇点连一条为 c[j] 的边，表示若不要该蛋糕，答案减少的量。众所周知最大流等于最小割，跑个网络流，然后这题我们就做完了。

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 3e5 + 10;//数组一定要开足
const int inf = 1e10;
int head[N], tot = 1, s, t, n, m, dis[N], now[N], g[N], c[N];
struct edge {
    int v, w, nxt;
} e[N];
inline void add(int u, int v, int w) {
    e[++ tot] = {v, w, head[u]};
    head[u] = tot;
}
inline bool bfs() {
    queue<int> q;
    for (int i = 0; i <= t; i ++)dis[i] = inf;
    dis[s] = 0;
    now[s] = head[s];
    q.push(s);
    while (q.size()) {
        int u = q.front();
        q.pop();
        for (int i = head[u]; i; i = e[i].nxt) {
            int v = e[i].v;
            if (e[i].w > 0 && dis[v] == inf) {
                dis[v] = dis[u] + 1;
                now[v] = head[v];
                q.push(v);
                if (v == t)return 1;
            }
        }
    }
    return 0;
}
inline int dfs(int u, int sum) {
    if (u == t)return sum;
    int res = 0;
    for (int i = now[u]; i && sum; i = e[i].nxt) {
        now[u] = i;
        int v = e[i].v;
        if (e[i].w > 0 && (dis[v] == dis[u] + 1)) {
            int k = dfs(v, min(sum, e[i].w));
            if (k == 0)dis[v] = inf;
            e[i].w -= k;
            e[i ^ 1].w += k;
            res += k;
            sum -= k;
        }
    }
    return res;
}//网络流板子
signed main() {
    int G;
    cin >> G >> n >> m;
    s = 0, t = n + m + 1;
    for (int i = 1; i <= n; i ++)cin >> c[i];
    for (int i = 1; i <= G; i ++)cin >> g[i];
    for (int i = 1; i <= m; i ++) {
        int x;
        cin >> x;
        add(s, i + n, x), add(i + n, s, 0);
    }//将源点向工具连一条t[i]的边
    int ans = 0;
    for (int i = 1; i <= n; i ++) {
        for (int j = 1; j <= G; j ++) {
            int x;
            cin >> x;
            c[i] -= g[j] * x;
        }//减去原料花费
        if (c[i] > 0)add(i, t, c[i]), add(t, i, 0), ans += c[i];
        //统计蛋糕的收益和
    }
    for (int i = 1; i <= n; i ++) {
        int k, x;
        cin >> k;
        while (k --) {
            cin >> x;
            add(x + n, i, inf);
            add(i, x + n, 0);
        }//对于i所需要的工具j，连一条从j到i边权为正无穷的边
    }
    while (bfs())ans -= dfs(s, inf);
    cout << ans << '\n';
    return 0;
}