题目：prim算法

题目链接：

53. 寻宝（第七期模拟笔试） (kamacoder.com)

代码：

#include<bits/stdc++.h>
#include<unordered_map>
#include<unordered_set>
using namespace std;
int main() {int v, e;int x, y, k;cin >> v >> e;vector<vector<int>>grid(v + 1, vector<int>(v + 1, 10001));while (e--) {cin >> x >> y >> k;grid[x][y] = k;grid[y][x] = k;}vector<int>minEdges(v + 1, 10001);vector<bool>Intree(v + 1, false);for (int i = 1; i < v; i++) {int cur = -1;int MinVal = INT_MAX;for (int j = 1; j <= v; j++) {if (!Intree[j] && minEdges[j] < MinVal) {cur = j;MinVal = minEdges[j];}}Intree[cur] = true;for (int j = 1; j <= v; j++) {if (!Intree[j] && grid[cur][j] < minEdges[j]) {minEdges[j] = grid[cur][j];}}}int result = 0;for (int i = 2; i <= v; i++) {result += minEdges[i];}cout << result << endl;
}

题目：kruskal算法

题目链接：

53. 寻宝（第七期模拟笔试） (kamacoder.com)

代码：

#include<bits/stdc++.h>
#include<unordered_map>
#include<unordered_set>
using namespace std;struct Edge {int l, r, val;
};
int n = 10001;
vector<int>father(n, -1);
void init() {for (int i = 0; i < n; i++) {father[i] = i;}
}
int find(int u) {if (u == father[u]) return u;else {return father[u] = find(father[u]);}
}
void join(int u, int v) {u = find(u);v = find(v);if (u == v) return;father[v] = u;}
static bool cmp(const Edge& a, const Edge& b) {return a.val < b.val;
}int main() {int v, e;int x, y, k;cin >> v >> e;vector<Edge>edges;while (e--) {cin >> x >> y >> k;edges.push_back({ x,y,k });}sort(edges.begin(), edges.end(), cmp);vector<Edge>result;init();int result_val = 0;for (Edge edge : edges) {int x = find(edge.l);int y = find(edge.r);if (x != y) {result.push_back(edge);result_val += edge.val;join(x, y);}}cout << result_val << endl;
}