P10541 [THUPC 2024 决赛] 研发计划 - Solution

· · 题解

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

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

将超级源汇分别设为 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;
}