To create a node set of connected parts, Prim algorithm adopts a greedy strategy to add the point with the minimum edge weight from the set to the set each time and iteraten
And then finally connect all the points.
Subject train of thought
Dist [I] : the minimum distance between node I and the set. St [I] : indicates whether node I has been added to the set.
- Outer loop iteration
n
Add all the points to the set. - Each time I iterate over the point closest to the set, if the point closest to the set is zero
0x3f
(infinity), it means that the minimum spanning tree cannot be generated, and impossible is output; If the distance is not zero0x3f
, represents reachable, and the edge weight is increased. - After the new node is added to the set, the new node is used as the fulcrum to update the distance between all other nodes and the set.
C + + code
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 510, INF = 0x3f3f3f3f;
int n, m;
int g[N][N];
int dist[N];
int st[N];
void Prim(a)
{
memset(dist, 0x3f.sizeof dist);
int res = 0;
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 (i && dist[t] == INF)
{
cout << "impossible";
return;
}
if (i)
{
res += dist[t];
}
st[t] = true;
for (int j = 1; j <= n; j++)
{
dist[j] = min(dist[j], g[t][j]);
}
}
cout << res;
}
int main(a)
{
cin.tie(0);
ios::sync_with_stdio(false);
memset(g, 0x3f.sizeof g);
cin >> n >> m;
while (m--)
{
int u, v, w;
cin >> u >> v >> w;
g[u][v] = g[v][u] = min(g[u][v], w);
}
Prim(a);return 0;
}
Copy the code