T138426 「MCOI-01」Zombie 僵尸

公元 2048 年，书虫玩上了 VR 版的 MC。 VR 版的 MC 每个玩家都有一个职业，而书虫是一名红石科学家。 有一天，书虫的家附近来了很多僵尸，书虫拿着自己的钻石剑去打僵尸，被打死了。 书虫很不甘心，他突然想起了自己以前的一个发明，可以将所有僵尸杀死。 于是书虫找到了那个发明，但他突然发现：这个发明用不了！ 这可怎么办啊？ 他将这个发明拆开，发现内部的红石因为太久没有使用被蠹虫全部吃了！

他找到了仅存的红石，准备将红石放上去。但他发现：红石被女巫施了魔法，每个方块上的红石只能连接相邻 **两个方块** 上的红石，**不能不连接或只连接一个，三个，四个**。并且，传播距离十分短，**假如两个红石之间没有中继器就 无法传播红石信号**。 发明可以看做一个 $ n \times m $ 的方格，有些地方有中继器，而这个发明，只有当所有红石和中继器形成 **多个或一个回路** 的时候，才能发挥作用，否则就会短路。而书虫没有太多的红石。 这个发明里放着一颗红石块，但书虫忘记放在哪个格子下了，不过一定不在中继器下。 众所周知红石块只能激活相邻的红石的红石信号，然而红石信号传播得不远就没了，这就必须使用书虫发明的小型红石中继器了，能够放在两个方块之间。 但在两个格子之间放置小型中继器是有代价的。 而书虫发现，这个发明的红石电路可能不能够形成一个闭合回路，这个时候书虫可以花费一些代价旋转大型中继器。 但因为书虫太弱了，能够花费的代价有限，他想尽量花费少一点儿的代价。 书虫还有炼金术师 TNT 送的 $ c $ 瓶药水，可以使在两个方块之间放置小型中继器的代价为 $ 0 $。 你能帮他计算最少花费多少代价能够成功地将僵尸击退吗？ 是的，你可以，A 了这道题吧。

无

无

#### 样例说明 对于样例 $1$，本身的线路分布为  然后我们可以旋转那个可爱的中继器，即  对于样例 $ 2 $，我们想好了绝妙的解释，但是赛前 1 ms 被外星人偷走了，所以只好不放解释。 #### 数据规模与约定 **本题采用捆绑测试。** - Subtask 0（5 pts） $\ $：其中一个数据点 $ k=0 $，$ c=20 $；另一个数据点 $ k=5 $，$ c=0 $。 - Subtask 1（15 pts）：满足性质 A。 - Subtask 2（25 pts）：满足性质 B。 - Subtask 3（55 pts）：无特殊限制。 对于 $100\%$ 的数据，$ 2 \leq n,m \leq 10 $，$ 0 \leq k \leq 10 $，$ 1 \leq g,l \leq 10^6 $，$ 0 \leq c \leq 20 $。 - 性质 A：所有大型中继器都用不上。 - 性质 B：所有大型中继器在同一行或同一列，且首尾相连。并且还有 $ g=10^6 $，$ 0 < l \leq 100 $，且不用旋转中继器。 **数据保证能够通过旋转形成闭合回路。** Subtask 0 计分方式为加和，Subtask 1,2,3 计分方式为取最小值。 #### 说明 Minecraft OI Round 1 D - Idea：limaopipi2022 - Solution/Std：limaopipi2022 - Data：一只书虫仔/limaopipi2022/\_TNT\_ - Tester：mini_necro