【模拟赛·食物中毒】

背景

WZOI的小组成员今天集体食物中毒，什么事情也不能干了，这是一件十分可怕的事。幸亏WZOI的Bqc同志十分在行化学，他可以马上制作出解药来……

问题描述

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”，不包含引号。

样例输入

输出

medicine.in

medicine.out

2 2 2 3 2 1 5 2 1 3 3 3 1 3 4 4 2 3 4 1 1 4

Impossible

Possible

3 样例解释对于样例的第三组数据，可行的方案有选取 1、3 和选取 2、4. 数据规模对于30%的数据，N≤10，M≤20；对于50%的数据，N≤20，M≤40；对于100%的数据，N≤20，M≤50；对于100%的数据，Mi≤50。保证测试数据的组数不超过100。时间限制 1s 提示同一种化学物质被描述偶数次，那么说明这种物质不存在；否则这种物质存在。

【题解】

①STD：暴搜，时间复杂度由于有T的存在是O(10⁸)左右

②我：

由于只管治病的物质,因此将治病的物质编号压入线性基，

然后查询能否构造11111……1111就是了。时间复杂度O(5*10⁶)

#include<stdio.h>
#include<cstring>
#include<algorithm>
#define Xor go(j,1,m)x[j]^=A[i][j]
#define go(i,a,b) for(int i=a;i<=b;i++)
int n,m,a[103],M,t,index[103],x[55];bool Prior[103];

struct Linear_Base
{
	int A[55][55],have[55];
	void Clear(){go(i,1,m){have[i]=0;go(j,1,m)A[i][j]=0;}}
	void Insert()
	{
		go(i,1,m)if(x[i]){if(!have[i]){have[i]=1;
		go(j,1,m)A[i][j]=x[j];i=m;}else Xor;}
	}
	bool Capable()
	{
		go(i,1,m)if(x[i]&&A[i][i])Xor;
		int sum=0;go(i,1,m)sum+=x[i];return sum==0;
	}
}Tool;

int main()
{
	freopen("medicine.in","r",stdin);
	freopen("medicine.out","w",stdout);
	
	while(~scanf("%d%d",&n,&m))
	{
		Tool.Clear();
		memset(Prior,0,sizeof(Prior));
		go(i,1,m)scanf("%d",a+i),Prior[a[i]]=1;
		std::sort(a+1,a+m+1);go(i,1,m)index[a[i]]=i;
		go(i,1,n){scanf("%d",&M);memset(x,0,sizeof(x));
		go(i,1,M){scanf("%d",&t);if(Prior[t])x[index[t]]^=1;}
		Tool.Insert();}go(i,1,m)x[i]=1;puts(Tool.Capable()?"Possible":"Impossible");
	}
	return 0;
}//Paul_Guderian