#P9691. Find the MST for Grid

    ID: 6329 传统题 2000ms 512MiB 尝试: 3 已通过: 2 难度: 7 上传者: 标签>CF2300提高+/省选-交换论证同向双指针一维前缀和

Find the MST for Grid

Source:

  • 京都大学プログラミングコンテスト 2020
  • Petrozavodsk Summer 2021, Day 1 Kyoto U Contest, Problem F

题目描述

有一张 n×mn\times m 的网格图,第 xx 行第 yy 列的格点记为 (x,y)(x,y),给定四个单调不降数组 A,B,C,DA,B,C,D,网格图的边权由这四个数组决定,具体的:

  • (x,y)(x,y) 和 (x+1,y)(x+1,y) 之间的边权为 Ax+ByA_x+B_y。
  • (x,y)(x,y) 和 (x,y+1)(x,y+1) 之间的边权为 Cx+DyC_x+D_y。

你需要求出这张网格图最小生成树的大小。

输入格式

第一行两个整数 n,mn,m 表示网格图大小。

第二行 n−1n-1 个整数 AiA_i 表示数组 AA。

第三行 mm 个整数 BiB_i 表示数组 BB。

第四行 nn 个整数 CiC_i 表示数组 CC。

第五行 m−1m-1 个整数 DiD_i 表示数组 DD。

输出格式

一行一个整数表示最小生成树大小。

样例

2 3
1
1 3 6
1 4
1 2
17

最小生成树包含如下五条边:

  • (1,1)−(2,1):2(1,1) - (2,1): 2
  • (1,1)−(1,2):2(1,1) - (1,2): 2
  • (1,2)−(1,3):3(1,2) - (1,3): 3
  • (1,2)−(2,2):4(1,2) - (2,2): 4
  • (2,2)−(2,3):6(2,2) - (2,3): 6

样例二见下发文件。

数据范围

对于所有数据,保证 2≤n,m≤1052\leq n,m\leq 10^5,1≤Ai,Bi,Ci,Di≤1061\leq A_i,B_i,C_i,D_i\leq 10^6。

保证 $A_i\leq A_{i+1}, B_i\leq B_{i+1}, C_i\leq C_{i+1}, D_i\leq D_{i+1}$。

测试点编号 n,m≤n,m\le 特殊性质
1∼61\sim 6 10310^3 无
7∼127\sim 12 10510^5 A,BA,B 数组中所有元素相同
13∼2013\sim 20 无