[#10066]「一本通 3.1 练习 1」新的开始

Prim + 前向星

#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = 400;
const int MAXM = MAXN * MAXN;
const int INF = 0x3f3f3f3f;
struct E {
	int u, v, w, nxt;
} edge[MAXM];
int tot = 0;
int head[MAXN];
void init() {
	memset(head, -1, sizeof head);
}
void add_edge(int u, int v, int w) {
	edge[tot].u = u;
	edge[tot].v = v;
	edge[tot].w = w;
	edge[tot].nxt = head[u];
	head[u] = tot++;
}
int n;
int ans;
bool vis[MAXN];
int dis[MAXN];
void prim() {
	memset(vis, false, sizeof vis);
	memset(dis, INF, sizeof dis);
	for(int i = head[0]; ~i; i = edge[i].nxt)
		if(dis[edge[i].v] > edge[i].w)
			dis[edge[i].v] = edge[i].w;
	vis[0] = true;
	ans = 0;
	while(true) {
		int k = 0;
		int minn = INF;
		for(int i = 0; i < n; i++) {
			if(!vis[i] && dis[i] < minn) {
				minn = dis[i];
				k = i;
			}
		}
		if(minn == INF) return;
		vis[k] = true;
		ans += dis[k];
		dis[k] = 0;
		for(int i = head[k]; ~i; i = edge[i].nxt)
			if(!vis[edge[i].v] && dis[edge[i].v] > edge[i].w)
				dis[edge[i].v] = edge[i].w;
	}
}
int main() {
	init();
	scanf("%d", &n);
	n++;
	for(int i = 1; i < n; i++) {
		int temp;
		scanf("%d", &temp);
		add_edge(0, i, temp);
		add_edge(i, 0, temp);
	}
	for(int i = 1; i < n; i++) {
		for(int j = 1; j < n; j++) {
			int temp;
			scanf("%d", &temp);
			add_edge(i, j, temp);
		}
	}
	prim();
	printf("%d", ans);
	return 0;
}

Kruskal + 前向星

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAXN = 400;
const int MAXM = MAXN * MAXN;
const int INF = 0x3f3f3f3f;
struct E {
	int u, v, w, nxt;
	bool operator < (const E &n) const {
		return w < n.w;
	}
} edge[MAXM];
int tot = 0;
int head[MAXN];
void init() {
	memset(head, -1, sizeof head);
}
void add_edge(int u, int v, int w) {
	edge[tot].u = u;
	edge[tot].v = v;
	edge[tot].w = w;
	edge[tot].nxt = head[u];
	head[u] = tot++;
}
int n;
int ans;
int fat[MAXN];
int tfind(int n) {
	if(fat[n] != n) fat[n] = tfind(fat[n]);
	return fat[n];
}
void kruskal() {
	ans = 0;
	sort(edge, edge + tot);
	for(int i = 0; i < n; i++) fat[i] = i;
	for(int i = 0; i < tot; i++) {
		if(tfind(edge[i].u) != tfind(edge[i].v)) {
			ans += edge[i].w;
			fat[tfind(edge[i].u)] = tfind(edge[i].v);
		}
	}
}
int main() {
	init();
	scanf("%d", &n);
	n++;
	for(int i = 1; i < n; i++) {
		int temp;
		scanf("%d", &temp);
		add_edge(0, i, temp);
		add_edge(i, 0, temp);
	}
	for(int i = 1; i < n; i++) {
		for(int j = 1; j < n; j++) {
			int temp;
			scanf("%d", &temp);
			add_edge(i, j, temp);
		}
	}
	kruskal();
	printf("%d", ans);
	return 0;
}