算法训练营|图论第7天 prim算法 kruskal算法
题目：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 = k;
grid = 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 && minEdges < MinVal) {
cur = j;
MinVal = minEdges;
}
}
Intree = true;
for (int j = 1; j <= v; j++) {
if (!Intree && grid < minEdges) {
minEdges = grid;
}
}
}
int result = 0;
for (int i = 2; i <= v; i++) {
result += minEdges;
}
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;
}
}
int find(int u) {
if (u == father) return u;
else {
return father = find(father);
}
}
void join(int u, int v) {
u = find(u);
v = find(v);
if (u == v) return;
father = 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;
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]