复兴提高DAY07最小生成树
2025-07-07 22:28:29
发布于：上海
9阅读
0回复
0点赞
T1【最小生成树】最小生成树
//kruskal
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 9;
struct node {
int x, y, z;
}a[maxn];
int fa[5009];
int get(int x) {
if (fa[x] == x) return x;
return fa[x] = get(fa[x]);
}
void merge(int x, int y) {
fa[get(x)] = get(y);
}
bool cmp(node A, node B) {
return A.z < B.z;
}
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) fa[i] = i;
for (int i = 0; i < m; i++) {
cin >> a[i].x >> a[i].y >> a[i].z;
}
sort(a, a + m, cmp);
int ans = 0, edge = 0;
for (int i = 0; i < m; i++) {
if (get(a[i].x) == get(a[i].y)) continue;
merge(a[i].x, a[i].y);
edge++;
ans += a[i].z;
}
if (edge == n - 1) cout << ans;
else cout << "orz";
return 0;
}
//prim
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
int a[5009][5009];
int d[5009], vis[5009];
int n, m;
bool prim() {
memset(d, 0x3f, sizeof(d));
memset(vis, 0, sizeof(vis));
d[1] = 0;
for (int i = 1; i <= n; i++) { //每次向集合T中加入一个点
int x = 0;
for (int j = 1; j <= n; j++) { //找到离T集合最近的点
if (!vis[j] && d[j] < d[x]) x = j;
}
if (x == 0) return false; //没有找到点，说明其他点都与T集合不连通
vis[x] = 1; //标记，相当于把点x加入T集合
for (int y = 1; y <= n; y++) { //去更新S集合的点到T集合的距离
if(!vis[y]) d[y] = min(d[y], a[x][y]);
}
}
return true;
}
int main() {
cin >> n >> m;
memset(a, 0x3f, sizeof(a));
for (int i = 0; i < m; i++) {
int x, y, z;
cin >> x >> y >> z;
a[x][y] = min(a[x][y], z);
a[y][x] = min(a[y][x], z);
}
if (prim()) {
int ans = 0;
for (int i = 2; i <= n; i++) ans += d[i];
cout << ans;
}
else cout << "orz";
return 0;
}
T2【最小生成树】畅通工程
//kruskal
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 9;
struct node {
int x, y, z;
}a[maxn];
int fa[5009];
int get(int x) {
if (fa[x] == x) return x;
return fa[x] = get(fa[x]);
}
void merge(int x, int y) {
fa[get(x)] = get(y);
}
bool cmp(node A, node B) {
return A.z < B.z;
}
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) fa[i] = i;
for (int i = 0; i < m; i++) {
cin >> a[i].x >> a[i].y >> a[i].z;
}
sort(a, a + m, cmp);
int ans = 0, edge = 0;
for (int i = 0; i < m; i++) {
if (get(a[i].x) == get(a[i].y)) continue;
merge(a[i].x, a[i].y);
edge++;
ans += a[i].z;
}
if (edge == n - 1) cout << ans;
else cout << "no";
return 0;
}
//prim
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
int a[5009][5009];
int d[5009], vis[5009];
int n, m;
bool prim() {
memset(d, 0x3f, sizeof(d));
memset(vis, 0, sizeof(vis));
d[1] = 0;
for (int i = 1; i <= n; i++) { //每次向集合T中加入一个点
int x = 0;
for (int j = 1; j <= n; j++) { //找到离T集合最近的点
if (!vis[j] && d[j] < d[x]) x = j;
}
if (x == 0) return false; //没有找到点，说明其他点都与T集合不连通
vis[x] = 1; //标记，相当于把点x加入T集合
for (int y = 1; y <= n; y++) { //去更新S集合的点到T集合的距离
if(!vis[y]) d[y] = min(d[y], a[x][y]);
}
}
return true;
}
int main() {
cin >> n >> m;
memset(a, 0x3f, sizeof(a));
for (int i = 0; i < m; i++) {
int x, y, z;
cin >> x >> y >> z;
a[x][y] = min(a[x][y], z);
a[y][x] = min(a[y][x], z);
}
if (prim()) {
int ans = 0;
for (int i = 2; i <= n; i++) ans += d[i];
cout << ans;
}
else cout << "no";
return 0;
}
T3【最小生成树】继续畅通工程
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 9;
struct node {
int x, y, z;
}a[maxn];
int fa[5009];
int get(int x) {
if (fa[x] == x) return x;
return fa[x] = get(fa[x]);
}
void merge(int x, int y) {
fa[get(x)] = get(y);
}
bool cmp(node A, node B) {
return A.z < B.z;
}
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) fa[i] = i;
for (int i = 0; i < m; i++) {
int ok;
cin >> a[i].x >> a[i].y >> a[i].z >> ok;
if (ok) a[i].z = 0;
}
sort(a, a + m, cmp);
int ans = 0, edge = 0;
for (int i = 0; i < m; i++) {
if (get(a[i].x) == get(a[i].y)) continue;
merge(a[i].x, a[i].y);
edge++;
ans += a[i].z;
}
if (edge == n - 1) cout << ans;
else cout << "orz";
return 0;
}
T4【最小生成树】拆除地毯
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 9;
struct node {
int x, y, z;
}a[maxn];
int fa[maxn];
int get(int x) {
if (fa[x] == x) return x;
return fa[x] = get(fa[x]);
}
void merge(int x, int y) {
fa[get(x)] = get(y);
}
bool cmp(node A, node B) {
return A.z > B.z;
}
int main() {
int n, m, k;
cin >> n >> m >> k;
for (int i = 1; i <= n; i++) fa[i] = i;
for (int i = 0; i < m; i++) {
cin >> a[i].x >> a[i].y >> a[i].z;
}
sort(a, a + m, cmp);
int ans = 0, edge = 0;
for (int i = 0; i < m; i++) {
if (get(a[i].x) == get(a[i].y)) continue;
merge(a[i].x, a[i].y);
edge++;
ans += a[i].z;
if (edge == k) break;
}
cout << ans;
return 0;
}
这里空空如也
有帮助，赞一个