算法训练营|图论第7天 prim算法 kruskal算法

题目：prim算法

题目链接：

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

1. #include<bits/stdc++.h>
2. #include<unordered_map>
3. #include<unordered_set>
4. using namespace std;
5. int main() {
6.         int v, e;
7.         int x, y, k;
8.         cin >> v >> e;
9.         vector<vector<int>>grid(v + 1, vector<int>(v + 1, 10001));
10.         while (e--) {
11.                 cin >> x >> y >> k;
12.                 grid[x][y] = k;
13.                 grid[y][x] = k;
14.         }
15.         vector<int>minEdges(v + 1, 10001);
16.         vector<bool>Intree(v + 1, false);
17.         for (int i = 1; i < v; i++) {
18.                 int cur = -1;
19.                 int MinVal = INT_MAX;
20.                 for (int j = 1; j <= v; j++) {
21.                         if (!Intree[j] && minEdges[j] < MinVal) {
22.                                 cur = j;
23.                                 MinVal = minEdges[j];
24.                         }
25.                 }
26.                 Intree[cur] = true;
27.                 for (int j = 1; j <= v; j++) {
28.                         if (!Intree[j] && grid[cur][j] < minEdges[j]) {
29.                                 minEdges[j] = grid[cur][j];
30.                         }
31.                 }
32.         }
33.         int result = 0;
34.         for (int i = 2; i <= v; i++) {
35.                 result += minEdges[i];
36.         }
37.         cout << result << endl;
38. }

复制代码

题目：kruskal算法

题目链接：

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

1. #include<bits/stdc++.h>
2. #include<unordered_map>
3. #include<unordered_set>
4. using namespace std;
6. struct Edge {
7.         int l, r, val;
8. };
9. int n = 10001;
10. vector<int>father(n, -1);
11. void init() {
12.         for (int i = 0; i < n; i++) {
13.                 father[i] = i;
14.         }
15. }
16. int find(int u) {
17.         if (u == father[u]) return u;
18.         else {
19.                 return father[u] = find(father[u]);
20.         }
21. }
22. void join(int u, int v) {
23.         u = find(u);
24.         v = find(v);
25.         if (u == v) return;
26.         father[v] = u;
28. }
29. static bool cmp(const Edge& a, const Edge& b) {
30.         return a.val < b.val;
31. }
33. int main() {
34.         int v, e;
35.         int x, y, k;
36.         cin >> v >> e;
37.         vector<Edge>edges;
38.         while (e--) {
39.                 cin >> x >> y >> k;
40.                 edges.push_back({ x,y,k });
41.         }
42.         sort(edges.begin(), edges.end(), cmp);
43.         vector<Edge>result;
44.         init();
45.         int result_val = 0;
46.         for (Edge edge : edges) {
47.                 int x = find(edge.l);
48.                 int y = find(edge.r);
49.                 if (x != y) {
50.                         result.push_back(edge);
51.                         result_val += edge.val;
52.                         join(x, y);
53.                 }
54.         }
55.        
56.         cout << result_val << endl;
57. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。