自动搬运

查看原文

来自洛谷，原作者为

	strcmp 每一个不曾起舞的日子，都是对生命的辜负

搬运于2025-08-24 22:59:01，当前版本为作者最后更新于2024-08-03 20:04:12，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

我们发现如果没有可以直接购买技术这个条件，那么直接建反图，这题就是一个裸的最大权闭合子图。

但是可以购买技术，稍微难处理了一点。

将超级源汇分别设为 $s,\,t$。我们考虑最大权闭合子图的思路，割掉就是不选。

我们购买相当于从原来的建图中搞出来一个点放到 $s$ 那边的联通块内，然后这个点的后继可以不用管。

肯定考虑将技术 $u$ 拆成入点 $u$ 和出点 $u'$。方便我们决策是自研还是购买。

如果选择自研，可以想到要用 $u'$ 去连接它的前置技术，边权自然是 $+\infty$.

可以想到 $u \to u'$ 的连边必定不是 $h$，否则我们的 $f$ 放到哪都不合适。如果 $u \to u'$ 的连边是 $f$，它被割就相当于我们直接购买了，可以忽略掉其后继结点。至于出点 $u'$ 连向汇点的权值，也就只能是 $h$ 了。

在原来的基础上跑最大权闭合子图即可。

#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = a; i <= b; i++)
#define mp make_pair
using namespace std;
typedef long long int ll;
using pii = pair<int, int>;
constexpr int maxn = 1e5 + 10;
const ll top = 114514191981000LL, inf = top * 1000;
struct edge { int to, nxt; ll w; } nd[maxn]; int h[maxn], cnt = 0;
inline void add(int u, int v, ll w) { nd[cnt].nxt = h[u], nd[cnt].to = v, nd[cnt].w = w, h[u] = cnt++; }
inline void addE(int u, int v, ll w) { add(u, v, w); add(v, u, 0); }
int T, s, t, n, m, p, q, cur[maxn], d[maxn], que[maxn], hd = 1, ta = 0; ll sum = 0;
inline int bfs() {
	memset(d, 0x3f, (t + 1) * sizeof(int));
	hd = 1, ta = 0; que[++ta] = t; d[t] = 0;
	while (hd <= ta) {
		int u = que[hd++];
		for (int i = h[u]; ~i; i = nd[i].nxt) {
			int v = nd[i].to;
			if (d[v] > d[u] + 1 && nd[i ^ 1].w) d[v] = d[u] + 1, que[++ta] = v;
		}
	}
	return d[s] < 1e9;
}
ll dfs(int u, ll fl) {
	if (u == t || !fl) return fl; ll nw = fl;
	for (int& i = cur[u]; ~i; i = nd[i].nxt) {
		if (d[u] != d[nd[i].to] + 1 || !nd[i].w) continue;
		ll c = nd[i].w, wv = dfs(nd[i].to, min(fl, c));
		if (!(nd[i].w -= wv, nd[i ^ 1].w += wv, fl -= wv)) return nw;
	}
	if (fl) d[u] = 1e9;
	return nw - fl;
}
inline void Dinic() { while (bfs()) memcpy(cur, h, sizeof(cur)), sum += dfs(s, inf); }
ll f[maxn], H[maxn], g[maxn];
int main() {
	memset(h, -1, sizeof(h));
	scanf("%d%d%d%d", &n, &m, &p, &q); s = 2 * n + m + 1, t = s + 1; ll ans = 0;
	rep(i, 1, n) scanf("%lld", &f[i]), addE(i, i + n, f[i]);
	rep(i, 1, n) scanf("%lld", &H[i]), addE(i + n, t, H[i]);
	rep(i, 1, m) scanf("%lld", &g[i]), addE(s, i + 2 * n, g[i]), ans += g[i];
	for (int i = 1, u, v; i <= p; i++) scanf("%d%d", &u, &v), addE(v + 2 * n, u, inf);
	for (int i = 1, u, v; i <= q; i++) scanf("%d%d", &u, &v), addE(v + n, u, inf); Dinic();
	printf("%lld\n", ans - sum);
	return 0;
}