P2762 太空飞行计划问题

选择一个项目，就必须连带选择它依赖的资源

问题

P2762 太空飞行计划问题
每个实验带来一笔收入，但执行它必须配置题目列出的若干仪器；仪器各有一次配置成本。要求选择实验和仪器，使收入减成本最大，并输出被选中的两类编号。

数据规模：$1\le m,n\le50$，收入与成本均小于 $2^{31}$；每个实验行的仪器编号数量不定。

本题和 P2057 善意的投票 有点类似，每个对象只有 “选择 / 不选择” 两种状态（是不是有点像 0/1 背包？）。

不过本题中的选择之间存在强制依赖，即：如果选择一个实验，那么它需要的所有仪器都必须同时被选择。

注：这种“选择一个点，就必须继续选择它所依赖的点”的集合称为闭合集合。

实验可以看作正权点，权值为收入；仪器可以看作负权点，权值为配置成本的相反数，题目要求的就是最大权闭合子图。

设所有实验收入之和为 sum，那么真正选择方案后会产生哪些损失呢？分析后发现只有两种：一种是某个实验没被选择，那么它的收入就缺失了；另一种是某个仪器被选择了，那么就必须支付它的费用。

所以实际的利润就可以写成：总收入 - 放弃实验收入 - 选择仪器成本。

于是求最大利益，其实就是求 “放弃实验收入 + 选择仪器成本” 之和的最小值，可以联想到最小割模型。

我们用源侧表示这个对象选择，汇侧表示这个对象不被选择。

对于实验 $i$，连接 $S\to i$，容量为实验收入。如果实验留在源侧，这条边不被割，表示取得这份收入；如果实验被放到汇侧，这个实验被舍弃，割容量增加实验收入，正好表示放弃这份收益。

对于仪器 $j$，连接 $j\to T$，容量为仪器成本。如果仪器位于汇侧，它没有被选择，不产生费用；如果仪器位于源侧，这个仪器被选中，需要支付对应容量，正好表示承担这份成本。

于是有限边的割容量就恰好等于 “放弃实验收入 + 选择仪器成本”。

最后处理特殊的依赖关系，由 P1345 奶牛的电信 中的边容量设定，最后还需要用 inf 边表达实验与仪器之间的强制依赖。

解释边容量

若实验 $i$ 依赖仪器 $j$，连接 $i\to j$，容量为 inf。如果实验 $i$ 位于源侧而仪器 $j$ 位于汇侧，就表示“选择了实验却没有选择必需仪器”，此时这条 inf 边会跨割。任何有限最优割都不会允许这种状态，所以自然强制得到“选择实验 $i$ $\Rightarrow$ 选择仪器 $j$”。

最大流结束后，最终残量网络中从 $S$ 仍然能够到达的点构成最小割的源侧。而我们已经规定源侧代表“选择”，所以这些可达的实验和仪器正好构成一个最优闭合集合。

方案恢复只需要重新在最终残量网络中做一次可达性搜索即可，这里代码使用的是 Dinic 最后一次 BFS 残留的 dep 状态判断，不算通用，理性看待。

▶

P2762 建图与方案恢复

namespace DINIC { /* 模板代码略 */ }
using namespace DINIC;

void solve( ) {
    int m = read( ), n = read( );
    
    int S = 0, T = m + n + 1;
    init( T );

    ll sum = 0;

    for( int i = 1; i <= m; ++ i ) {
        int x = read( );
        sum += x;
        add_edge( S, i, x );
        string s;
        getline( cin, s );
        stringstream ss( s );
        while( ss >> x ) add_edge( i, m + x, inf );
    }

    for( int i = m + 1; i <= m + n; ++ i ) {
        int x = read( );
        add_edge( i, T, x );
    }

    ll flow = Dinic( S, T, T );
    for( int i = 1; i <= m; ++ i ) {
        if( dep[i] != -1 ) cout << i << ' ';
    }
    cout << '\n';

    for( int i = m + 1; i <= m + n; ++ i ) {
        if( dep[i] != -1 ) cout << i - m << ' ';
    }
    cout << '\n';
    cout << sum - flow << '\n';
}

复盘

这道题不能把最大流值直接理解成最终利润。最大流等于的是最小割，也就是为了满足依赖关系不得不承担的最小损失，真正收益需要用总实验收入 sum 减去它。