H×WH \times WH×W 的二维平面,∀0≤i≤H,0≤j≤W\forall 0\le i\le H, 0\le j\le W∀0≤i≤H,0≤j≤W 有一个点。连接 (i,j)(i, j)(i,j) 到 (i+1,j)(i + 1, j)(i+1,j) 的边权为 pip_ipi(0≤j≤W0\le j\le W0≤j≤W),连接 (i,j)(i, j)(i,j) 到 (i,j+1)(i, j + 1)(i,j+1) 的边权为 qjq_jqj。求这张 (H+1)×(W+1)(H + 1)\times (W + 1)(H+1)×(W+1) 个点的图的最小生成树的边权和。1≤H,W≤1051\le H, W\le 10^51≤H,W≤105,1≤pi,qj≤1081\le p_i,q_j\le 10^81≤pi,qj≤108。
Translated by @YangTY
使用您的 gxyz 通用账户