裸的 Kruskal

#include<iostream>
#include<algorithm>

using namespace std;

const int maxn = 5010;
const int maxm = 200010;

int n, m;
int fa[maxm];
int ans;
int amt;

struct Edge {
	int from, to, w;
} e[maxm];
int cnt;

void add(int u, int v, int w) {
	e[cnt++].from = u;
	e[cnt].to = v;
	e[cnt].w = w;
	return;
}

int get(int x) {
	if (fa[x] == x) {
		return fa[x];
	} else {
		return fa[x] = get(fa[x]);
	}
}

void init() {
	for (int i = 0;i < maxn;i++) {
		fa[i] = i;
	}
	return;
}

void merge(int x, int y) {
	x = get(x), y = get(y);
	if (x != y) {
		fa[x] = y;
	}
	return;
}

bool cmp(Edge a, Edge b) {
	return a.w < b.w;
}

int main() {
	init();
	cin >> n >> m;
	
	for (int i = 1;i <= m;i++) {
		for (int j = 1;j <= m;j++) {
			int x;
			cin >> x;
			if (i < j && x != 0) {
				add(i, j, x);
			}
		}
	}
	
	for (int i = 1;i <= m;i++) {
		add(0, i, n);
	}
	
	sort(e + 1, e + 1 + cnt, cmp);
	
	for (int i = 1;i <= cnt;i++) {
		if (get(e[i].from) != get(e[i].to)) {
			merge(e[i].from, e[i].to);
			ans += e[i].w;
			amt ++;
		}
	}
	
	cout << ans << endl;
	return 0; 
}