题目名称 805. [WZOI 2011 S3] 食物中毒
输入输出 medicine.in/out
难度等级
时间限制 1000 ms (1 s)
内存限制 128 MiB
测试数据 10
题目来源 GravatarMakazeu 于2012-06-12加入
开放分组 全部用户
提交状态
分类标签
搜索法
分享题解
通过:23, 提交:69, 通过率:33.33%
GravatarMakazeu 100 0.164 s 0.31 MiB C++
GravatarHale 100 0.175 s 13.66 MiB C++
GravatarTruth.Cirno 100 0.224 s 0.29 MiB C++
GravatarTruth.Cirno 100 0.225 s 0.29 MiB C++
GravatarTruth.Cirno 100 0.227 s 0.29 MiB C++
GravatarTruth.Cirno 100 0.228 s 0.29 MiB C++
GravatarTruth.Cirno 100 0.233 s 0.29 MiB C++
GravatarTruth.Cirno 100 0.233 s 0.29 MiB C++
GravatarTruth.Cirno 100 0.234 s 0.29 MiB C++
GravatarTruth.Cirno 100 0.234 s 0.29 MiB C++
本题关联比赛
20120809
关于 食物中毒 的近10条评论(全部评论)
bitset带DFS,妙啊
多组数据要清空,报零两行泪
5000积分祭
GravatarHale
2019-10-29 20:32 3楼
是高斯消元?
Gravatarwangyucheng
2013-11-03 21:32 2楼
以后要记住,超过longint,连1都要用1ll。。
Gravatar苏轼
2012-10-23 10:14 1楼

805. [WZOI 2011 S3] 食物中毒

★   输入文件:medicine.in   输出文件:medicine.out   简单对比
时间限制:1 s   内存限制:128 MiB

Problem 1  食物中毒 (medicine.pas/c/cpp)

 

 

背景

 

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

 

问题描述

 

Bqc经过一段时间的研究发现,要解这种毒需要一种特殊的药物。不幸的是,这种药物在市面上不存在,没有办法Bqc只好亲自制得这种药物。它含有M种化学物质A1,A2,,AM。现 在Bqc的手上有N种药材(每种药材只有一种),每种药材含有若干种化学物质(Bqc他有一种 机器,只要将药材放入机器,就能制得相应的药物)。

Bqc需要你的帮助,他希望你能帮他选取若干种药材,用这些选取的药材制作出Bqc需要 的药物。由于这些化学物质是有毒的,因此你选出来的药物,必须含有这M种化学物质。

有一点需要注意:根据中医以毒攻毒的理论,两个相同的化学物质在一起,它们的药性会 同时消失变为一种无毒物质(大多情况下这种无毒物质会挥发掉,也就是说这种化学物质消 失了)。比如说药材1有化学物质1、2,药材2有化学物质1、3,那么如果药材1和药材2混合, 你得到的药物会含有化学物质2、3。

Bqc问你,需要选用那些药材可以制得他想要的药物?

 

输入格式

 

本题每个测试点存在多组数据,每组输入数据第1行包含两个整数NM,表示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

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



样例解释

 

对于样例的第三组数据,可行的方案有选取 1、3 和选取 2、4.

 

数据规模

 

对于30%的数据,N10M20; 

对于50%的数据,N20M40; 对于100%的数据,N20M50

对于100%的数据,Mi50。 保证测试数据的组数不超过100。

 

时间限制

1s

 

提示

 

同一种化学物质被描述偶数次,那么说明这种物质不存在;否则这种物质存在。