算法原理
根据 (operatorname{Kruskal}) 算法的运算规则，每次总是会把当前边权最小，且连接着本不连通的两个点的边选中。
而在这道题目中，位于同一行或列的边的边权大小一定是相同的，因此一定会接连选完这一行或列上所有可行的边。
思考过程
选择一行/列后，整个被选中的行/列上所有的点都位于同一个连通分量。
故选完至少一行和至少一列后，接下来构成生成树的过程中，一定保证只存在一个包含两个及以上节点的连通分量。
这是一个关键点，思考过程可以以这个点分成两部分。
-
在选完至少一行和一列之前，保证接下来选择的任何行/列，这一行/列上所有的边都会被选择。
-
而在选完至少一行和一列之后，对于即将被选择的一行来说，这一行上尚未被连接进最小生成树的点的个数 (=) 总的列数 (-) 已被选择的列数。而一条边在构建最小生成树时，只能将一个点与最小生成树连接起来。因此选择这一行能选择的边的条数，即等于这一行上尚未接入最小生成树的点的个数。即总列数 (-) 已被选择的列数。对于列来说同理。
因此总的算法思路就明确了：
-
首先将所有的边权值放到一起升序排列，注意记录一下这个边权是横边的边权还是纵边的边权，开一个
pair存很方便（自动按照第一关键字为索引进行升序排序）。一遍sort进行排序。开两个变量 (l ext{(line)})、(c ext{(column)}) 存储已经选择的行/列数。 -
然后从小到大枚举排序后的边权，在两个统计变量都不为 (0) 之前，任何选的行/列都将其所包含的所有边全部加入最小生成树。
-
在两个统计变量都大于 (0) 之后，对于行来说，加入其包括的 (m-c) 条边，即可保证这一行上所有的点全部加入最小生成树，且不会影响到之后的选择，故可以保证正确性。列同理。
Tips
- 排序时把所有的边放在了一起，因此记得把数组开成两倍。
- 不开
long long见祖宗
代码：
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int Maxe = 3e5 + 5;
pair<LL, bool> a[Maxe << 1];
int n, m;
LL ans = 0;
int main()
{
scanf("%d%d", &n, &m);
for(register int i = 1; i <= n; ++i)
{
int x;
scanf("%d", &x);
a[i] = make_pair(x, false);
}
for(register int i = n + 1; i <= n + m; ++i)
{
int x;
scanf("%d", &x);
a[i] = make_pair(x, true);
}
sort(a + 1, a + n + m + 1);
int l = 0, c = 0;
for(register int i = 1; i <= n + m; ++i)
{
if(!a[i].second)
{
if((!l)||(!c))
{
ans += (long long)(m - 1) * a[i].first;
}
else
{
ans += (long long)(m - c) * a[i].first;
}
l++;
}
else
{
if((!l)||(!c))
{
ans += (long long)(n - 1) * a[i].first;
}
else
{
ans += (long long)(n - l) * a[i].first;
}
c++;
}
}
printf("%lld", ans);
return 0;
}