核心思路

1. 问题转化

设：

• $u_i = x_i - x_{i-1}$（第 $i$ 列的宽度）
• $v_j = y_j - y_{j-1}$（第 $j$ 行的高度）

则地块 $(i,j)$ 的面积 = $u_i \times v_j$。

居民要求：$u_{a_k} \times v_{b_k} = p_k$。

问题转化为：找到正整数 $u_1,\dots,u_n$ 和 $v_1,\dots,v_m$，满足上述等式约束，并最小化： [ \left(\sum_{i=1}^n u_i\right) \times \left(\sum_{j=1}^m v_j\right) ]

2. 图论建模

将行和列看作二分图：

• 左部：$n$ 个列节点
• 右部：$m$ 个行节点
• 边：居民要求 $(a_k, b_k, p_k)$ 对应连接列 $a_k$ 和行 $b_k$ 的边，权值为 $p_k$

约束 $u_a \times v_b = p$ 等价于： [ \frac{u_a}{1} = \frac{p}{v_b} ] 即 $u_a$ 和 $v_b$ 成比例关系。

3. 连通分量处理

对每个连通分量，我们可以确定节点值之间的比例关系。

代码中：

• num[x] / den[x] 表示节点 $x$ 的相对值
• 从起点 $s$ 开始 BFS，利用约束 $u_a \times v_b = p$ 传播比例关系

例如：从 $u_1 = 1$ 开始，若边 $(1, b_1, p_1)$，则 $v_{b_1} = p_1 / u_1 = p_1$。

若发现矛盾（比例不一致），输出 NIE。

4. 整数化处理

对于连通分量，我们确定的是相对比例。需要找到最小的正整数解。

设分量中有：

• 列节点集合 $X$，行节点集合 $Y$
• 已知比例：$u_i = \alpha_i \cdot t$，$v_j = \beta_j / t$（$t$ 为缩放因子）

则约束 $u_i \times v_j = p_{ij}$ 自动满足。

最小化目标中，该分量的贡献为： [ \sum_{i \in X} u_i = t \cdot \sum \alpha_i ] [ \sum_{j \in Y} v_j = \frac{1}{t} \cdot \sum \beta_j ]

分量总贡献 = $\left(t \cdot \sum \alpha_i\right) \times \left(\frac{1}{t} \cdot \sum \beta_j\right) = \left(\sum \alpha_i\right) \times \left(\sum \beta_j\right)$

与 $t$ 无关！

5. 关键优化

实际上，不同连通分量之间可以独立缩放。但代码通过枚举因子 $d$ 来处理可能的整数约束，确保所有 $u_i, v_j$ 为整数。

最终问题转化为：

• 每个连通分量有固定贡献 $(S_x, S_y)$ 到总宽度和总高度
• 总宽度 $X = \sum S_x$，总高度 $Y = \sum S_y$
• 总面积 $X \times Y$

通过排序和贪心调整分量顺序，找到最小面积。

重要公式

1. 面积约束： [ u_i \times v_j = p_{ij} ]

2. 比例传播： [ \frac{u_a}{u_{a'}} = \frac{p_{ab}}{p_{a'b}} \cdot \frac{v_b}{v_b} = \frac{p_{ab}}{p_{a'b}} ]

3. 分量贡献： [ \text{宽度贡献} = \sum_{i \in \text{cols}} u_i,\quad \text{高度贡献} = \sum_{j \in \text{rows}} v_j ]

4. 总面积： [ \text{Area} = \left(\sum_{\text{分量}} S_x\right) \times \left(\sum_{\text{分量}} S_y\right) ]

算法流程

1. 建图：行列二分图，边权为面积要求
2. 连通分量：BFS 确定比例关系，检查一致性
3. 整数化解：计算每个分量的 $(S_x, S_y)$ 贡献
4. 组合优化：通过排序调整使 $X \times Y$ 最小
5. 输出：最小总面积

复杂度

• 建图：$O(l)$
• BFS：$O(n + m + l)$
• 排序：$O(\text{分量数} \times \log)$
• 总体：$O(n + m + l)$ 或稍高，可接受