<—点个赞吧QwQ
宣传一下算法提高课整理{:target=”_blank”}
Kruskal算法
先介绍一下“完全图”的定义:
一个无向图结构的$n$个节点中,如果任意一个节点都和其他$n-1$个节点直接连接,那么这个图结构就叫做完全图,$n$个节点的完全图记作$K_n$
对于有向图的$K_n$定义,则需要把“直接连接”改为“直接的双向连接”
下图就是$n=1,2,3,4$时$K_n$的样子:
显而易见的是,单独的一个节点就已经构成$K_1$了,而Kruskal算法执行开始之前,所有的节点都可以视作$K_1$
所以我们要做的就是,在按照Kruskal算法连接两个节点的时候,计算一下将这两个节点所属连通块一同扩展为完全图,需要额外连接多少条边。对于分属两个不同连通块的节点$s$和节点$e$,可以保证它们在连上之前,所属的连通块就已经是完全图了(假设分别是$K_p$和$K_q$),将其连接起来并扩展为完全图,就需要$s$所属连通块的每个节点都和$e$所属连通块的全部$q$个节点连一条边,总数为$p\*q$,但同时又得去掉$(s,e)$这条边,因此总数为$p\*q-1$
另外这额外连接的每条边,由于不能影响扩展后最小生成树的结构,故权值都得大于$(s,e)$的权值$v$,每条边最小权值都得$v+1$,因此每一轮扩展都需要累加$(v+1)\*(p\*q-1)$
计算连通块的大小,可以借助Kruskal算法用到的并查集实现,其余细节见注释
时间复杂度
$O(n\*logn)$
C++ 代码
#pragma GCC optimize(2)
#include <iostream>
#include <algorithm>
#include <numeric>
#include <vector>
#include <tuple>
using namespace std;
using Edge = tuple<int, int, int>;
class UnionFind {
private:
//多一条初始全1的cnt表,记录每个节点所属连通块的节点总数
vector<int> ori, cnt;
int find(int x) {
if (x != ori[x]) ori[x] = find(ori[x]);
return ori[x];
}
public:
UnionFind(int n) {
ori.resize(n + 1);
cnt.resize(n + 1);
iota(ori.begin(), ori.end(), 0);
fill(cnt.begin(), cnt.end(), 1);
}
//求出连接s和e后扩充为完全图需要增加多少条边
int extendToComplete(int s, int e) {
int pr = find(s), nx = find(e);
if (pr == nx) return 0;
/*
* 先求后连
* 将s和e连接之后,还要将s和e所属连通块中的节点两两相连
* 新连接的边数等于s和e所属连通块大小的乘积减去1(要去掉s,e之间的那条)
*/
int res = cnt[pr] * cnt[nx] - 1;
ori[pr] = nx;
cnt[nx] += cnt[pr];
return res;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--) {
vector<Edge> edges;
int n;
cin >> n;
UnionFind uf(n);
for (int i = 1; i < n; i++) {
int s, e, v;
cin >> s >> e >> v;
edges.push_back({ v,s,e });
}
sort(edges.begin(), edges.end());
int ans = 0;
for (auto& ed : edges) {
int v = get<0>(ed), s = get<1>(ed), e = get<2>(ed);
//新连接的边,权值必须比这条边大,要不然最小生成树可能选不到这条边你
ans += (v + 1) * uf.extendToComplete(s, e);
}
cout << ans << endl;
}
return 0;
}
btw,这个问题和“走廊泼水节”有什么关系(