[CSP-S 2019 江西] 网格图

知识点

最小生成树、排序、前缀和

解题思路

利用行列边权相同的结构，选最便宜行、列作十字骨架。答案为min(a)(m-1)+min(b)(n-1)，再对其余行列交点加min(a_i,b_j)。排序b并做前缀和，可批量求每行的贡献。

正确性说明

按Kruskal从小到大处理整行横边、整列竖边：第一条横行和第一条竖列形成十字连通骨架；对其余行列的交点，最先能把它并入已形成网格连通结构的方向恰为两权较小者。因此批量计数得到骨架两项与每个剩余交点的min之和。相等边按任意固定顺序处理，不改变总权。

易错点

n×m可达9×10^10，不能建点建边；骨架行列不能再次计交点；答案用64位。

复杂度

时间O(n log m+m log m)，空间O(n+m)。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int n,m;cin>>n>>m;vector<long long>a(n),b(m);for(auto&x:a)cin>>x;for(auto&x:b)cin>>x;sort(a.begin(),a.end());sort(b.begin(),b.end());vector<long long>p(m+1);for(int i=0;i<m;i++)p[i+1]=p[i]+b[i];long long ans=a[0]*(m-1)+b[0]*(n-1);for(int i=1;i<n;i++){int k=upper_bound(b.begin()+1,b.end(),a[i])-b.begin();ans+=p[k]-p[1]+a[i]*(m-k);}cout<<ans<<'\n';}