#P2673. [Wf2011]Chips Challenge

    ID: 1730 传统题 1000ms 128MiB 尝试: 155 已通过: 64 难度: 8 上传者: 标签>CF2500提高+/省选-枚举较小维度补集转化供需平衡建模最小费用最大流势能优化费用流Dijkstra

[Wf2011]Chips Challenge

题目描述

有一个芯片,芯片上有 N×N(1≤N≤40)N \times N (1 \leq N \leq 40) 个插槽,可以在里面装零件。 有些插槽不能装零件,有些插槽必须装零件,剩下的插槽随意。 要求装好之后满足如下两条要求:

  • 第 ii 行和第 ii 列的零件数目必须一样多(1≤i≤N1 \leq i \leq N)。
  • 第 ii 行的零件数目不能超过总的零件数目的 AB\frac{A}{B}(1≤i≤N1 \leq i \leq N,0≤A≤B≤10000 \leq A \leq B \leq 1000,B≠0B \neq 0)。

求最多可以另外放多少个零件(就是除掉必须放的)。如果无解输出 impossible。

输入格式

输入包含多个测试用例。

每个用例以包含三个整数的一行开始:芯片的大小 NN,以及 AA 和 BB 这两个已经描述的整数。接下来的 NN 行包含 NN 个字符描述的插槽,其中包括'.'、'/'和'C'。

最后一个测试用例后跟随一行包含三个零的输入。

输出格式

对于每个测试用例,显示一行开始为测试实例编号。如果有解,显示可以添加到芯片上的零件的最大数量。如果不存在解决方案,则显示“impossible”。

请遵循示例输出的格式。

输入样例

2 1 1
/.
//
2 50 100
/.
C/
2 100 100
./
C.
5 3 10
CC/..
././/
..C.C
/.C..
/./C/
5 2 10
CC/..
././/
..C.C
/.C..
/./C/
0 0 0

输出样例

Case 1: 0
Case 2: 1         
Case 3: impossible
Case 4: 7         
Case 5: impossible