[数据结构与算法]2.15 每日总结

kruskal (克鲁斯卡尔算法)

以边为单位，进行排序

运用结构体，把x，y（两个边）z（距离）存到结构体中

sort快排对进行排序

	struct node {
		int x,y,z;
	}edge[maxn];
	
	bool cmp(node a,node b) {
		return a.z < b.z;
	}

    for(int i = 1; i <= m; i ++) {
		cin >> edge[i].x >> edge[i].y >> edge[i].z;
	}

    sort(edge + 1,edge + 1 + m,cmp);

P3366 【模板】最小生成树

#include <bits/stdc++.h>

using namespace std;

const int maxn = 2e5 + 10; 

struct node {
	int x,y,z;
}edge[maxn];

bool cmp(node a,node b) {
	return a.z < b.z;
}

int fa[maxn];
int n,m;
long long sum;

int get(int x) {
	return x == fa[x] ? x : fa[x] = get(fa[x]);
}

int main(void) {
	cin >> n >> m;
	for(int i = 1; i <= m; i ++) {
		cin >> edge[i].x >> edge[i].y >> edge[i].z;
	}
	for(int i = 0; i <= n; i ++) {
		fa[i] = i;
	}
	sort(edge + 1,edge + 1 + m,cmp);
	for(int i = 1; i <= m; i ++) {
		int x = get(edge[i].x);
		int y = get(edge[i].y);
		if(x == y) continue;
		fa[y] = x;
		sum += edge[i].z;
	}
	int ans = 0;
	for(int i = 1; i <= n; i ++) {
		if(i == fa[i]) ans ++;
	}
	if(ans > 1) puts("orz");
	else cout << sum;
	return 0;
} 

此题就是用kruskal (克鲁斯卡尔算法)来做的

prim (普里姆算法)

以点为单位来进行

在一个只有源点的集合中，每次

	// prim 算法求最小生成树 
	
	#include <cstdio>
	#include <string>
	#include <cstring>
	#include <iostream>
	#include <algorithm>
	
	#define INF 0x3f3f3f3f
	
	using namespace std;
	
	const int maxn = 505;
	
	int a[maxn][maxn];
	
	int vis[maxn],dist[maxn];
	
	int n,m;
	
	int u,v,w;
	
	long long sum = 0;
	
	int prim(int pos) {
		dist[pos] = 0;
		// 一共有 n 个点,就需要 遍历 n 次,每次寻找一个权值最小的点,记录其下标
		for(int i = 1; i <= n; i ++) {
			int cur = -1;
			for(int j = 1; j <= n; j ++) {
				if(!vis[j] && (cur == -1 || dist[j] < dist[cur])) {
					cur = j;
				}
			}
			// 这里需要提前终止
			if(dist[cur] >= INF) return INF;
			sum += dist[cur];
			vis[cur] = 1;
			for(int k = 1; k <= n; k ++) {
			    // 只更新还没有找到的最小权值
				if(!vis[k]) dist[k] = min(dist[k],a[cur][k]);
			}
		}
		return sum;
	}
	
	int main(void) {
		scanf("%d%d",&n,&m);
		memset(a,0x3f,sizeof(a));
		memset(dist,0x3f,sizeof(dist));
		for(int i = 1; i <= m; i ++) {
			scanf("%d%d%d",&u,&v,&w);
			a[u][v] = min(a[u][v],w);
			a[v][u] = min(a[v][u],w);
		}
		int value = prim(1);
		if(value >= INF) puts("impossible");
		else printf("%lld\n",sum);
		return 0;
	} 

都加入一个点，最短的点，一直循坏下去