最小生成树

• Kruskal
• Prim

结尾

图解

#include 
using namespace std;
double S, tol;
int n, m, pre[100005], k;
struct edge{
    int u, v;
    double w;
    bool operator<(const edge b) const{
        return w < b.w;
    }
}e[100005];
int find(int x){
    while(x != pre[x]) x = pre[x];
    return x;
}
void join(int x, int y){
    pre[find(x)] = find(y);
}
int main(){
    cin >> S >> n;
    int u, v;
    double w;   
    while(cin >> u >> v >> w){
        e[++m].u = u, e[m].v = v, e[m].w = w;
    }   
    for(int i = 1; i <= n; ++i) pre[i] = i;
    sort(e + 1, e + 1 + m); 
    for(int i = 1; i <= m; ++i) {
        if(k == n - 1) break;
        if(find(e[i].u) != find(e[i].v)){
            k++;
            tol += e[i].w;
            join(e[i].u, e[i].v);
        }
    }
    if(tol > S || k < n - 1){
        cout << "Impossible" << endl;
    }else {
        cout << "Need " << fixed << setprecision(2) << tol << " miles of cable" << endl;
    }
    return 0;
}

图解
不知道哪些人会舍弃简单的kruskal来用prim

#include 
#define N 1005
using namespace std;
int lc[N], mst[N], g[N][N];
int n, m;
int prim(){
	int sum = 0;
	for(int i = 2; i <= n; ++i) lc[i] = g[1][i], mst[i] = 1;
	for(int i = 2; i <= n; ++i){
		int minx = INT_MAX, mink = 0;
		for(int j = 2; j <= n; ++j){
			if(lc[j] < minx && lc[j] != 0) minx = lc[j], mink = j;
		}
		sum += lc[mink];
		lc[mink] = 0;
		for(int j = 2; j <= n; ++j){
			if(g[mink][j] < lc[j]) lc[j] = g[mink][j], mst[j] = mink;
		}
	}
	return sum;
}
int main(){
	memset(g, 0x3f, sizeof(g));
	cin >> n >> m;
	for(int i = 1; i <= m; ++i){
		int u, v, w;
		cin >> u >> v >> w;
		g[u][v] = g[v][u] = w;
	}		
	cout << prim() << endl;
	return 0;
}

结尾

本文只是博主自己的学习笔记，初学者可能会看不懂，建议在[图解]链接中去学习其他大佬的博客