P11025 [COTS 2020] 辣椒 Sadnice

译自 [Izborne Pripreme 2020 (Croatian IOI/CEOI Team Selection)](https://hsin.hr/pripreme2020/) D1T3。$\texttt{3s,0.5G}$。

花园里种了辣椒。花园可以被描述为一张 $(N+1)\times (M+1)$ 的网格图，其中辣椒被种在格点上。她还用 $[(N+1)\times (M+1)-1]$ 条绳索连接相邻的格点，使得任意两株辣椒都能通过绳索互相到达。换句话说，绳索构成了这个网格图的生成树上的边。 定义两棵辣椒**连通**，当且仅当它们通过绳索直接或间接相连。 晚上有人要来搞破坏。破坏者会在水平方向或者竖直方向划一刀，将划过的绳索全部切断。切断后，辣椒植株会被分成几个连通块。**破坏者会让连通块的数量尽量多。** 怎么安排绳索，才能使得被切断后连通块的数量最小？

无

无

#### 评分方式 若你输出的解是最优解，得该测试点的满分。 否则，按照如下方式计算得分倍数： $$K=0.75\times \max\left\{\left(\frac{A-1}{B-1}\right)^4,1-\left(1-\frac{1}{(B-A)^2}\right)^6\right\}$$ 其中 $A$ 为最优的答案，$B$ 为你构造方案的答案。 你将获得 $K$ 倍测试点得分的分数。子任务得分为子任务内测试点得分最小值。 例如，样例 $1$ 输出得满分。样例 $2$ 输出得 $75\%$ 的分数。 #### 数据范围 对于 $100\%$ 的数据，保证 $1\le N\le M\le 1\, 000$。 | 子任务编号 | $N,M\le $ | 特殊性质 | 得分 | | :--: | :--: | :--: | :--: | | $ 1 $ | $1\,000$ | A |$ 15 $ | | $ 2 $ | $1\,000$ | B |$ 15 $ | | $ 3 $ | $3$ | |$ 5 $ | | $ 4 $ | $10$ || $ 10 $ | | $ 5 $ | $100$ | | $ 20 $ | | $ 6 $ | $1\, 000$ || $ 35 $ | - 特殊性质 A：$N=M$。 - 特殊性质 B：$2N=M$。