知識點：最小生成樹
原題面： 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，轉載請聲明出處。