解题思路
本题在 n≤25 的规模下求固定大小 k 的最大权独立集,并输出所有最优解,适合状压枚举:
- 建图:用位掩码
conflict_mask[i] 记录与策略 i+1 互斥的策略集合(conflicts 为 1 下标)。
- 枚举子集:遍历
mask ∈ [0, 2^n),用 popcount(mask) == k 筛出大小为 k 的组合。
- 独立集判定:对
mask 中每个置位 i,检查 conflict_mask[i] & mask 是否为 0;非 0 表示选中了互斥对。
- 维护最优:统计权重和,保留最大权;同权则全部保留。按
mask 递增枚举,内层编号自然升序,组合字典序与枚举顺序一致。
- 无解:若没有任何合法
mask,返回 []。