知识点：最小生成树
原题面： Luogu
扯
感觉挺秒的一道题，如果理解了 Kruscal 的本质的话比较好想。
“连有”总是打出来“镰鼬”，想到了寒假看的《怨恋》。
该怎么评价它呢= =
只能说画风比较喜人（
题意简述
给定一 \(n\times m\) 的网格图，边有边权，第 \(r\) 行第 \(c\) 列的点可表示为 \((r,c)\)。
点 \((i,j)\) 与 \((i,j+1)\) 间连有一条权值为 \(a_i\) 的边，其中 \(1\le i\le n, 1\le j<m\)。
点 \((i,j)\) 与 \((i+1,j)\) 间连有一条权值为 \(b_j\) 的边，其中 \(1\le i< n, 1\le j\le m\)。
求最小生成树各边的权值和。
\(1\le n,m\le 3\times 10^5\)，\(1\le a_i,b_j\le 10^5\)。
分析题意
题意挺抽象的，把样例画出来，发现长这样：
每一行，每一列的边权值相同。
考虑直接建图跑 Kruscal，复杂度 \(O(nm\log nm)\)。
获得了 64pts 的好成绩。
考虑上述算法中 Kruscal 进行时的过程。
同 行/列 的边权相等，对边按权值排序后，它们一定在新的顺序中相邻。
考虑同 行/列 的边被添加的情况。
若它们连接的点 此时全部不连通，则它们会被连续地添加到生成树中。
否则，会选择此时不连通的点之间的边进行添加。
从点的角度看：
答案即为，将所有点添加到生成树中的最小花费。
考虑加边对点的影响，添加新边后，不会影响旧点在树中的出现情况。
则上述两情况结果相同，都是将该 行/列 中所有点添加到树中。
则可以得到一个神奇的算法：
将 整行/整列 整体考虑。
对于情况 1，需要把该 行/列 所有的边全部添加，相当于将该 行/列 添加到树中。
对于情况 2，其需要添加的边数，显然为该 行/列 中，已经被添加到生成树中的点数。
其值等于该 行/列 的边数 \(-\) 已经被添加的 列/行 数。
在添加边时维护树中的 行/列 数即可。
一开始先对输入的 \(n+m\) 条边排序，之后遍历它们。
复杂度 \(O((n+m)\log (n+m) + n+m)\)。
爆零小技巧
代码实现
//知识点：最小生成树
/*
By:Luckyblock
*/
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstring>
#define ll long long
const int kMaxn = 3e5 + 10;
//=============================================================
int n, m, a[kMaxn], b[kMaxn], linked_x, linked_y;
ll ans;
//=============================================================
inline int read() {
int f = 1, w = 0;
char ch = getchar();
for (; !isdigit(ch); ch = getchar())
if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
return f * w;
}
//=============================================================
int main() {
n = read(), m = read();
for (int i = 1; i <= n; ++ i) a[i] = read();
for (int j = 1; j <= m; ++ j) b[j] = read();
std :: sort(a + 1, a + n + 1);
std :: sort(b + 1, b + m + 1);
ans += 1ll * (m - 1) * a[1] + 1ll * (n - 1) * b[1];
linked_x ++, linked_y ++;
for (int i = 2, j = 2; i <= n && j <= m; ) {
if (a[i] <= b[j]) {
ans += 1ll * (m - linked_y) * a[i];
++ linked_x, ++ i;
} else {
ans += 1ll * (n - linked_x) * b[j];
++ linked_y, ++ j;
}
}
printf("%lld", ans);
return 0;
}
作者@Luckyblock，转载请声明出处。