克鲁斯卡尔(Kruskal)算法求最小生成树

/*

 *Kruskal算法求MST

*/

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <string>

#include <algorithm>

#include <queue>

#include <set>

#include <stack>

using namespace std;

const int MAXN = 110;					//最大点数

const int MAXM = 10000;					//最大边数

int F[MAXN];							//并查集使用 

struct Edge {

	int u, v, w;

}edge[MAXM];						//存储边的信息，包括起点/终点/权值 

int tol = 0;		//记录边数 

void addedge(int u, int v, int w) {

	edge[tol].u = u;

	edge[tol].v = v;

	edge[tol++].w = w;

}

bool cmp(Edge a, Edge b) {			//排序函数，将边按照权值从小到大排序

	return a.w < b.w;

}

int find(int x) {

	if (F[x] == -1)

		return x;

	else

		return F[x] = find(F[x]);

}

int Kruskal(int n) {		//传入点数，返回最小生成树的权值，如果不连通返回-1

	memset(F, -1, sizeof(F));

	sort(edge, edge+tol, cmp);

	int cnt = 0;			//计算加入的边数

	int ans = 0;

	for (int i = 0; i<tol; i++) {

		int u = edge[i].u;

		int v = edge[i].v;

		int w = edge[i].w;

		int t1 = find(u);

		int t2 = find(v);

		if (t1 != t2) {

			ans += w;

			F[t1] = t2;

			cnt ++ ;

		}

		if (cnt == n-1)

			break;

	}

	if (cnt < n-1)

		return -1;

	else

		return ans;

}

int main() {

	int t;

	cin >> t;

	while (t --) {

		tol = 0;

		memset(edge, 0, sizeof(edge));

		int n, m;

		cin >> n >> m;

		while (m --) {

			int x, y, w;

			cin >> x >> y>> w;

			addedge(x, y, w);

		}

		int res = Kruskal(tol);

		if (res == -1)

			cout << "Not Unique!"<< endl;

		else

			cout << res << endl;

	}

	return 0;

}
巴特西

克鲁斯卡尔(Kruskal)算法求最小生成树

最新文章

热门文章
