题目大意

有 $N$ 种药和 $N$ 种药材，每种药使用若干种药材。选择 $K$ 种药，如果这些药使用的药材总数也恰好是 $K$，则这些药有效，体重变化为这些药的 $P_i$ 之和；否则无效。求最佳体重变化（可以不吃药，即体重不变）。

关键条件：存在完美匹配，即每种药都能唯一对应一种药材。

算法分析

1. 条件转化

题目中的条件 "K 种减肥药使用的药材并集大小也为 K" 是 Hall 定理的直接应用。

Hall 定理：二分图存在完美匹配的充要条件是，对于左部点的任意子集 $S$，其邻居节点数 $|N(S)| \geq |S|$。

题目保证存在完美匹配，因此对于所有药剂的子集都满足 Hall 条件：$|N(S)| \geq |S|$。

我们要找的是满足 $|N(S)| = |S|$ 的子集 $S$，这样的子集能够形成一个完美匹配的组成部分。

2. 问题重构

我们需要找出所有满足 药材并集大小 = 药的数量 的药集 $S$，计算 $\sum_{i \in S} P_i$，并求最大值。

由于保证完美匹配，这样的子集包括：

• 空集（体重变化为 0）
• 任何能够形成完美匹配子图的药集

3. 算法选择

方法一：状压DP（适合 N ≤ 20）

对于小数据范围，我们可以用状态压缩枚举所有子集：

for (int mask = 0; mask < (1 << N); mask++) {
    int drug_count = __builtin_popcount(mask);
    int herb_count = 0;
    // 计算这些药的药材并集
    for (int i = 0; i < N; i++) {
        if (mask >> i & 1) {
            herb_count |= herb_mask[i];
        }
    }
    herb_count = __builtin_popcount(herb_count);
    
    if (drug_count == herb_count) {
        // 计算该子集的P_i和，更新答案
    }
}

时间复杂度：$O(2^N \cdot N)$

方法二：利用完美匹配性质（N ≤ 300）

由于存在完美匹配，我们可以将问题转化为在匹配图上寻找最优子图。

关键观察：满足条件的子集对应原图的一个子图，其中每个连通分量都是强连通的（在转化为有向图后）。

我们可以用动态规划求解：

• 将二分图转化为有向图
• 使用 Tarjan 算法找出强连通分量
• 对每个强连通分量，计算其权重和
• 选择所有权重为正的强连通分量

代码实现（状压DP版本）

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int N;
    cin >> N;
    
    vector<int> herb_mask(N, 0);
    for (int i = 0; i < N; i++) {
        int t;
        cin >> t;
        for (int j = 0; j < t; j++) {
            int herb;
            cin >> herb;
            herb_mask[i] |= (1 << (herb - 1));
        }
    }
    
    vector<int> P(N);
    for (int i = 0; i < N; i++) {
        cin >> P[i];
    }
    
    long long ans = 0;  // 不吃药的情况
    
    // 枚举所有非空子集
    for (int mask = 1; mask < (1 << N); mask++) {
        int drug_count = __builtin_popcount(mask);
        int herb_union = 0;
        long long sum = 0;
        
        for (int i = 0; i < N; i++) {
            if (mask >> i & 1) {
                herb_union |= herb_mask[i];
                sum += P[i];
            }
        }
        
        int herb_count = __builtin_popcount(herb_union);
        
        if (drug_count == herb_count) {
            ans = max(ans, sum);
        }
    }
    
    cout << ans << endl;
    return 0;
}

复杂度分析

• 时间复杂度：$O(2^N \cdot N)$，适用于 N ≤ 20
• 空间复杂度：$O(N)$

总结

本题的核心是理解 Hall 定理在匹配问题中的应用。对于小数据范围，直接枚举验证是可行的方法；对于大数据范围，需要利用图论算法和动态规划来优化。