[bzoj 3438] 小M的作物

两块无限大的耕地A,B, n种作物的种子. 第i种作物种到A中获得ai的收益, 种到B中获得bi的收益 (不能同时种到A,B). 另有m个组合, 第i个组合中的ki种作物同时种到A中获得c1i的额外收益, 同时种到B中获得c2i的额外收益. 求最大总收益. (1≤k<n≤1000, 0<m≤1000, 保证所有数据及结果不超过2*10^9) [bzoj 3894] 文理分科 与之同理.

让我们尝试用最大权闭合子图建模. 闭合图面临的是选与不选, 而作物面临的是种到A或B. 先假设全部种到B, 获得所有bi和c2i的收益, 现在选择一些种到A.

每种作物一个点, 每个组合拆成两个点1, 2. 选择点i的收益是(ai-bi). 如果某组合中有一种作物种到A, 则失去c2i的收益; 该组合中所有点向2连边. 如果某组合中的所有作物种到A, 则得到c1i的收益; 1向该组合中所有点连边. 由于求的是最大权闭合子图, 所以, 组合中所有点被选中, 1也将被选中. 最小割解之即可.

有另外一种建模方法, 会多连n条边: 【bzoj3438】小M的作物 最小割 - Oxer的专栏

讨论一下哪些边可能存在于最小割中, 发现这样是正确的......需要一点脑洞?

const int inf = 2e9;

namespace MinimumCut {
	const int N = 3002;
	
	struct Edge {
		int v, c;
	};
	vector<Edge> E;
	vector<int> adj[N];

	inline void add(int u, int v, int c)
	{
		adj[u].push_back(E.size());
		E.push_back((Edge){v, c});
		adj[v].push_back(E.size());
		E.push_back((Edge){u, 0});
	}

	int s, t, n, lv[N], cur[N];

	bool bfs()
	{
		queue<int> Q;
		Q.push(s);
		fill_n(lv, n, -1);
		lv[s] = 0;

		while (!Q.empty()) {
			int u = Q.front();
			Q.pop();
			rep (i, 0, adj[u].size()) {
				Edge& e = E[adj[u][i]];
				if (e.c && lv[e.v] == -1) {
					lv[e.v] = lv[u] + 1;
					Q.push(e.v);
				}
			}
		}

		return lv[t] != -1;
	}

	int dfs(int u, int f)
	{
		if (u == t) return f;
		int res = f;
		for (int& i = cur[u]; i < (int)adj[u].size(); ++i) {
			Edge& e = E[adj[u][i]];
			if (lv[e.v] == lv[u] + 1 && e.c) {
				int d = dfs(e.v, min(e.c, res));
				res -= d;
				e.c -= d;
				E[adj[u][i]^1].c += d;
				if (!res) break;
			}
		}
		return f - res;
	}

	int minimum_cut(int _s, int _t, int _n)
	{
		s = _s, t = _t, n = _n;
		int f = 0;
		while (bfs()) {
			fill_n(cur, n, 0);
			f += dfs(s, inf);
		}
		return f;
	}
}

using MinimumCut::add;

#define S 0
#define T (n+2*m+1)
#define P(i) (i)
#define C(i, j) (n+2*(i-1)+j)

const int N = 1000;
int a[N+1], b[N+1];

int main()
{
	int n, m, sum = 0;
	scanf("%d", &n);
	rep (i, 1, n+1)
		scanf("%d", &a[i]);
	rep (i, 1, n+1)
		scanf("%d", &b[i]);
	scanf("%d", &m);
	rep (i, 1, n+1) {
		sum += b[i];
		if (a[i] > b[i]) {
			sum += a[i] - b[i];
			add(S, P(i), a[i] - b[i]);
		} else
			add(P(i), T, b[i] - a[i]);
	}

	rep (i, 1, m+1) {
		int k, c1, c2, id1 = C(i, 1), id2 = C(i, 2);
		scanf("%d%d%d", &k, &c1, &c2);
		sum += c1 + c2;
		add(S, id1, c1);
		add(id2, T, c2);
		while (k--) {
			int x;
			scanf("%d", &x);
			add(id1, P(x), inf);
			add(P(x), id2, inf);
		}
	}

	printf("%d\n", sum - MinimumCut::minimum_cut(S, T, 2+n+2*m));
	return 0;
}