#P4087. [Sdoi2015]模拟电路

[Sdoi2015]模拟电路

[SDOI2015] 模拟电路

题目描述

一块芯片有 N×NN\times N 个插槽。每个插槽最多可放一个稳压组件。部分插槽不可用或已装有组件,你只能在开放且未被占用的插槽中安装新组件。

设安装后的组件总数为 CC,第 ii 行、第 jj 列中的组件数分别是 Ri,CjR_i,C_j。总数、行数和列数均计入原有的组件。芯片须满足以下条件:

  • 对于第 ii 行,给定 TiT_i 个列编号 ri,1,…,ri,Tir_{i,1},\ldots,r_{i,T_i}。若该列表非空,则 Ri≤∑j=1TiCri,jR_i\le\sum_{j=1}^{T_i}C_{r_{i,j}};列表为空时,第 ii 行没有这一项限制。
  • 对于每个 ii,给定比例 si,tis_i,t_i(0≤si,ti≤10\le s_i,t_i\le1)。第 ii 行的组件数不得超过 siCs_i C,第 ii 列的组件数不得超过 tiCt_i C。

求最多可安装多少个新组件。

输入格式

第一行一个正整数 NN(1≤N≤401\le N\le40),表示芯片的边长。接下来 NN 行,每行 NN 个字符,分别用 .、/、C 表示开放、不可用和已被组件占据的插槽。

接下来 NN 行描述行约束。第 ii 行先给出非负整数 TiT_i,再给出 TiT_i 个互不相同的列编号,均在 11 到 NN 之间。

接下来一行给出 s1,…,sNs_1,\ldots,s_N,最后一行给出 t1,…,tNt_1,\ldots,t_N。每个比例小数点后至多三位。

输出格式

如果可以达到要求,输出最多可新装的组件数;否则输出 impossible。

数据范围

  • 对于 5%5\% 的数据,1≤N≤41\le N\le4。
  • 存在 45%45\% 的数据,所有 Ti=0T_i=0;其中占全部数据 15%15\% 的部分没有已被占据的插槽。
  • 存在 20%20\% 的数据,所有 Ti=1T_i=1,且 ri,1=ir_{i,1}=i。

样例 #1

样例输入 #1

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

样例输出 #1

7

样例 #2

样例输入 #2

5
CC/..
././/
..C.C
/.C..
/./C/
1 1
1 2
1 3
1 4
1 5
0.2 0.2 0.2 0.2 0.2
0.2 0.2 0.2 0.2 0.2

样例输出 #2

impossible

样例说明

样例 1 每行、每列至多容纳总数的 3/103/10。以下是安装 77 个新组件的一种方案,W 表示新组件:

CC/W.
W/W//
W.C.C
/.CWW
/W/C/

![原题给出的样例 1 可行布局](file://circuit-sample-1.png)