<—点个赞吧QwQ
宣传一下算法提高课整理{:target=”_blank”}
Kruskal算法 $O(n + m*log(m))$
最小生成树问题,不过由于边被分成了必选和可选两部分,所以只需要在可选边中按最小生成树算法求解即可
Kruskal算法没啥需要细说的了,不过还是按照投题解的习惯写了较为详细的注释
时间复杂度
$O(n + m*log(m))$,n,m分别为节点总数和边总数
C++ 代码
#include <iostream>
#include <algorithm>
#include <numeric>
#include <functional>
#include <vector>
#include <tuple>
using namespace std;
using Edge = tuple<int, int, int>;
//跑一次kruskal,只选可选道路
int ans = 0, n, m, p, u, v, w;
vector<int> origin;
vector<Edge> edges;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
origin.resize(n + 1);
iota(origin.begin(), origin.end(), 0);
//kruskal算法要用到并查集
//如果要用lambda表达式写递归函数,必须指定function类实例的所有模板参数
function<int(int)> find = [&find](int x)->int {
if (x != origin[x]) origin[x] = find(origin[x]);
return origin[x];
};
//这个函数的作用是判断两个顶点是否一开始就相连,如果不相连则将他俩连起来
function<bool(int, int)> isConnected = [=](int s, int e)-> bool {
int pr = find(s), nx = find(e);
if (pr == nx) return true;
origin[pr] = nx;
return false;
};
while (m--) {
cin >> p >> u >> v >> w;
if (u < v) swap(u, v);
if (p == 1) {
ans += w;
isConnected(u, v);//不用管它的返回值,只需要将他俩连起来就可以
}
else {
edges.push_back({ w,u,v });//可选边加入备选表中,等待排序
}
}
sort(edges.begin(), edges.end());
//不用管选了多少条边,因为选到最后一定能保证整个图连通
for (Edge& edge : edges) {
int val = get<0>(edge), s = get<1>(edge), e = get<2>(edge);
if (isConnected(s, e)) continue;
ans += val;
}
cout << ans << endl;
return 0;
}