<—点个赞吧QwQ
宣传一下算法提高课整理{:target=”_blank”}
Kruskal算法 $O(n + k * log(k))$
非常裸的最小生成树问题
除去一些连线,使得网络中没有回路且不影响连通性,表明了留下的边是连通了原图中所有节点的树结构
去除边的$\Sigma f(i,j)$最大,就意味着留下的边$\Sigma f(i,j)$最小
那就意味着求出最小生成树的边权总和,再用原图中边权的总和去减,就是最后的结果
节点数量最大值100,可以用prim算法,但最大边数也才200,用Kruskal算法影响不大
Kruskal算法细节见注释
时间复杂度
$O(n + k * log(k))$,n是节点总数,k是边总数
C++ 代码
#include <iostream>
#include <algorithm>
#include <numeric>
#include <functional>
#include <vector>
#include <tuple>
using namespace std;
//以下的Graph类同时封装了图结构的信息和并查集信息
class Graph
{
private:
vector<tuple<int, int, int>> edges;//随意存储边,因为Kruskal算法是从最小的边开始选取的
vector<int> ori;//并查集用
int rest = 0;//统计边权总和
//并查集之“查”
int find(int x) {
if (x != ori[x]) ori[x] = find(ori[x]);
return ori[x];
}
//并查集之“并”,同时可以判断两个节点是否原本就连通
bool isConnected(int s, int e) {
int pr = find(s), nx = find(e);
if (pr == nx) return true;
ori[pr] = nx;
return false;
}
public:
//构造一个节点数n,边数m的图结构
Graph(int n, int m) {
//初始化并查集
ori.resize(n + 1);
iota(ori.begin(), ori.end(), 0);
//确定每条边
while (m--) {
int s, e, v;
cin >> s >> e >> v;
edges.push_back({ v,s,e });
rest += v;
}
//按照权值升序排序,用来运行Kruskal算法(时间复杂度的主要产生处)
sort(edges.begin(), edges.end());
}
int maxCostOfCutting() {
//Kruskal算法核心:每次选取权值最小的边,保证连接上之后不成环
//不用刻意控制连接成功的次数,反正遍历整个边集合之后,最多也就连接n-1次
for (tuple ed : edges) {
int s = get<1>(ed), e = get<2>(ed), v = get<0>(ed);
if (isConnected(s, e)) continue;
//从原图边权总和中减掉
rest -= v;
}
return rest;
}
};
int main() {
int n, m;
cin >> n >> m;
Graph G(n, m);
cout << G.maxCostOfCutting() << endl;
return 0;
}