最小生成树专题

Prim算法

#include <bits/stdc++.h>
using namespace std;
const int N = 510;
const int inf = 0x3f3f3f3f;
int g[N][N];
int n, m;
int dist[N];
bool st[N];
int prim()
{int retv = 0;memset(dist, 0x3f, sizeof dist);for(int i = 0; i < n; i++){int t = -1;for(int j = 1; j <= n; j++){if(!st[j] && (t == -1 || dist[t] > dist[j]))t = j;}if(dist[t] == inf && i) return inf;if(i) retv += dist[t];st[t] = true;for(int j = 1; j <= n; j++)dist[j] = min(dist[j], g[t][j]);}return retv;
}
int main()
{cin >> n >> m;memset(g, 0x3f, sizeof g);for(int i = 1; i <= m; i++){int a, b, c;cin >> a >> b >> c;g[a][b] = g[b][a] = min(g[a][b], c);}int t = prim();if(t == inf) cout << "impossible";else cout << t;
}

Prim算法的二叉堆优化版（一般不用）

Kruskal算法

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10, M = 2e5+10;
const int inf = 0x3f3f3f3f; 
int cnt, p[M];
struct edge{int a;int b;int c;bool operator<(const edge& u){return c < u.c;}
} e[M];
int n, m;
int find(int x)
{if(p[x] != x) p[x] = find(p[x]);return p[x];
}
int kruskal()
{int retv = 0;sort(e+1, e+m+1);for(int i = 1; i <= n; i++)p[i] = i;for(int i = 1; i <= m; i++){int a = find(e[i].a), b = find(e[i].b);if(a != b){p[a] = b;retv += e[i].c;cnt++;}}if(cnt < n-1) return inf;else return retv;
}
int main()
{cin >> n >> m;for(int i = 1; i <= m; i++){int a, b, c;cin >> a >> b >> c;e[i] = {a, b, c};}int t = kruskal();if(t == inf) cout << "impossible";else cout << t;
}