#P3325. [SDOI2015] 模拟电路

[SDOI2015] 模拟电路

题目描述

一家著名的芯片公司希望您能帮他们在一些最新的产品上安装可以稳定电压的组件。每块芯片都被设计成 N×MN\times M 的带插槽的正方形,一个插槽可以安装一块单独的组件,你的任务是尽可能多地插入这些组件。

现代处理器的设计是很复杂的。为了可以稳定电压,你要面对下面几个限制:一些插槽是不可用的。一些插槽已经被其它的组件占据了,因而无法被新的组件使用。内存总线要连接到芯片的水平和垂直的边界上,它们的负载电压需要是安全的。

具体来说,芯片公司提供了 NN 组限制条件,分别对应了 NN 行。其中对于第 ii 行以及第 ii 组限制条件,给定非负整数 TiT_iTiT_i 个列编号,记为 ri,jr_{i,j}1jTi1\le j\le T_i),要求满足:第 ii 行的组件数目不能超过指定的 TiT_i 个列方向上组件数目的和(也就是不超过“第 ri,1r_{i,1} 列的组件数目 ++ri,2r_{i,2} 列的组件数目 ++ \cdots”)。为了避免插槽过热,给定浮点数 sis_i1iN1\le i\le N) 且 0si10\le s_i\le 1,要求第 ii 行的组件数不超过总组件数的 sis_i。同样给定浮点数 tit_i1iN1\le i\le N)且 0Ti10\le T_i\le 1,要求第 ii 列的组件数不超过总组件数的 tit_i

需要注意的是,已经占据了位置的组件,在统计一行或一列组件总数时,也是要被考虑在内的。而在计算芯片总组件数时.也要将已经占据了位置的组件考虑进去。芯片被描述为一个 NN 行,每行 NN 个字符的矩阵,其中 . 表示开放插槽,/ 表示不可用插槽,C 表示插槽已被一个组件占据。

输入格式

第一行给定 11 个正整数,表示芯片的规模 NN1N401\le N\le 40)。

然后给出 NN 行,每行 NN 个字符描述插槽,字符为 ./C 之一,含义如上所述。

之后 NN 行,描述了限制条件。其中第 ii 行首先给出非负整数 TiT_i,表示第 ii 行的限制条件涉及到的列的个数。之后再给出 TiT_i 个不重复的整数(都在 11NN 的范围中),描述了相关的列。

再下一行,给出了 NN 个浮点数依次对应 sis_i。每一个数字小数点后不超过三位。

再下一行,给出了 NN 个浮点数依次对应 tit_i。每一个数字小数点后不超过三位。

输出格式

如果存在合法的策略,输出最多可以再在芯片上安装多少个组件。否则输出 impossible

5
CC/..
././/
..C.C
/.C..
/./C/
1 1
1 2
1 3
1 4
1 5
0.3 0.3 0.3 0.3 0.3
0.3 0.3 0.3 0.3 0.3
7