问题描述
Bqc经过一段时间的研究发现，要解这种毒需要一种特殊的药物。不幸的是，这种药物在 市面上不存在，没有办法Bqc只好亲自制得这种药物。它含有M种化学物质A1,A2,…,AM。现 在Bqc的手上有N种药材(每种药材只有一种)，每种药材含有若干种化学物质(Bqc他有一种 机器，只要将药材放入机器，就能制得相应的药物)。
Bqc需要你的帮助，他希望你能帮他选取若干种药材，用这些选取的药材制作出Bqc需要 的药物。由于这些化学物质是有毒的，因此你选出来的药物，必须含有这M种化学物质。 有一点需要注意：根据中医以毒攻毒的理论，两个相同的化学物质在一起，它们的药性会 同时消失变为一种无毒物质(大多情况下这种无毒物质会挥发掉，也就是说这种化学物质消 失了)。比如说药材1有化学物质1、2，药材2有化学物质1、3，那么如果药材1和药材2混合， 你得到的药物会含有化学物质2、3。 Bqc问你，需要选用那些药材可以制得他想要的药物？
输入格式
本题每个测试点存在多组数据，每组输入数据第1行包含两个整数N和M，表示Bqc拥有的 药材数目和他所需药物所含的化学物质的种类数目；
第2行共有M个整数，分别表示M中化学物质的编号，用1~50之间的数字编号(输入数据保 证同一种化学物质不会被描述多次)；
第3行到第N+2行，每行包含若干个数。第i+2行的第一个数为Mi，表示药材i包含Mi中化 学物质，接下来Mi个数，描述药材i含有的化学物质的编号，用1~50之间的数字编号(同一种 化学物质可能会被描述多次)。 每组输入数据用一个空行隔开。
输出格式
对于每组数据输出一行，如果用这些药材可以制得Bqc需要的药物，那么输出“Possible”； 否则输出“Impossible”，不包含引号。
样例输入
2 2
2 3
2 1 5
2 1 3
3 3
1 3 4
4 2 3 4 1
1 4
2 2 1
4 4
1 2 3 4
3 1 3 4
3 1 4 5
1 2
2 2 3
样例输出
Impossible
Possible
Possible
其实吧，这道题我把它画成图，我还以为可以用二分图匹配做，后来发现tan90°，然后就只有用状压了，毕竟这个选到指定种类的题很容易想到用二进制表示状态
然后就是一个暴力搜索了，原本是打着死马当活马医的态度做这题，结果竟然还一次就A了
【思路】
数组f[i]表示第i个数含有哪些物质（二进制表示），然后暴力搜索；
有个叫大米兔的大佬还提出了更强的解法，就是用线性基，优化了很多啊
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cstdlib>
#define maxn 55
#define ll long long
using namespace std; ll f[maxn];
ll goal,n,m;
int vis[maxn],y[maxn],tr=; int read(){
int xx=,ff=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')ff=-;ch=getchar();}
while(ch>=''&&ch<=''){xx=xx*+ch-'';ch=getchar();}
return xx*ff;
} void dfs(int pos,ll now){
if(tr==)return;
if(now==goal){printf("Possible\n");tr=;return ;}
if(pos==n+)return;
if(!vis[pos]){
vis[pos]=;dfs(pos+,now^f[pos]);vis[pos]=;
}
if(tr==)return;
dfs(pos+,now);
} int main(){
freopen("medicine.in","r",stdin);
freopen("medicine.out","w",stdout);
while(~scanf("%lld%lld",&n,&m)){
goal=;memset(f,,sizeof(f));tr=;
memset(vis,,sizeof(vis));
memset(y,,sizeof(y));
for(int i=;i<=m;i++){
int a;a=read();y[a]++;
goal^=1ll<<(a-);
}
for(int i=;i<=n;i++){
int k;k=read();
for(int j=;j<=k;j++){
int a;a=read();
if(y[a])f[i]^=1ll<<(a-);
}
}dfs(,);
if(!tr)printf("Impossible\n");
}
}
我dfs打的丑不要笑，主要是习惯了以dep为参数的dfs，这次以pos的还有点不熟悉QAQ