题解：P10541 [THUPC 2024 决赛] 研发计划

xubaichuan · 2026-06-10 11:52:44 · 题解

很有启发价值的一题。

你会发现这题和最大权闭合子图板子的唯一区别在于，获取技术既可以购买，也可以研发。这出现了一个“或”的逻辑，而板子貌似只有“与”的逻辑。

但如果我们先不考虑购买，直接建图，会发现：不管怎么把边“并入”这张图，都无法描述“或”的逻辑。

换句话说，逻辑最大权闭合子图中的逻辑“或”本来就不能通过“并联”描述。

考虑拆点。记 s, t 分别为超级源点、超级汇点，A_{in}(i) 和 A_{out}(i) 分别表示「研发技术 i」「使用技术 i」，B(j) 表示「产品 j」，重新连边：

答案就是 \sum\limits_{j=1}^m g_j 减去最小割。

注意到，我们拆点后，相当于把购买和研发“串联”，这样只要割掉购买、研发任意一项就能保证不连通。

这就是本题最大的价值：在以最大权闭合子图为例的最小割模型里，“并联”表示逻辑“与”，“串联”表示逻辑“或”。

核心代码：

int main() {
    int n, m, p, q;
    cin >> n >> m >> p >> q;
    int s = n * 2 + m + 1, t = s + 1;
    long long sum = 0;

    for (int i = 1, f; i <= n; i++) {
        cin >> f;
        add_edge(i, i + n, f);
    }
    for (int i = 1, h; i <= n; i++) {
        cin >> h;
        add_edge(s, i, h);
    }
    for (int i = 1, g; i <= m; i++) {
        cin >> g;
        sum += g;
        add_edge(i + n * 2, t, g);
    }
    for (int u, v; p--; ) {
        cin >> u >> v;
        add_edge(u + n, v + n * 2, inf);
    }
    for (int u, v; q--; ) {
        cin >> u >> v;
        add_edge(u + n, v, inf);
    }

    cout << sum - maxflow(s, t) << '\n';
    return 0;
}