题解：P13847 [CERC 2023] Cakes

#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;
}