最小生成树模板

prim 算法 按点算，适合于点少的情况

邻接矩阵，时间复杂度 o(n^2)

//PTA公路村村通 
#include<iostream>
#include<cstdio>
using namespace std;
const int INF = 0x3fffffff;
const int MAXV = 1005;
int G[MAXV][MAXV], d[MAXV];//G存两个城镇直接的距离，d存已标记点到此点的最短距离 
bool vis[MAXV];//vis存是否被标记过 
int prim(int n)
{
	int ans = 0;//边权最小值 
	fill(vis,vis+MAXV,false);
	fill(d, d + MAXV, INF);
	d[1] = 0;//从第一个城镇开始 
	for (int i = 0; i < n; i++)//n个点，循环n次 
	{
		int u = -1, Min = INF;//Min存放最小d[u],u点的d[u]最小 
		for (int j = 1; j <= n; j++)//寻找未访问点中最小d[] 
		{
			if (vis[j] == false && d[j] < Min)
			{
				u = j;
				Min = d[j];
			}
		}
		if (u == -1)return -1;//不连续，无法连成一棵树 
		vis[u] = true;//标记已访问 
		ans += d[u];
		for (int k = 1; k <= n; k++)//更新与u点连接的最优值 
		{
			//k未访问&&k能到达u&&u为中介点使k离集合更短 
			if (vis[k] == false && G[u][k] != INF&&G[u][k] < d[k])
				d[k] = G[u][k];
		}
	}
	return ans;
}
int main()
{
	int n, m, i, a, b, c, ans;//n代表城镇个数，m代表路径个数 
	while(scanf("%d %d",&n,&m)!=EOF&&n)
	{
	    fill(G[0], G[0] + MAXV*MAXV, INF);//G初始化为没有任何路径连通 
	for (i = 0; i < m; i++)
	{
		cin >> a >> b >> c;//输入两个城镇与权值 
		G[a][b] = G[b][a] = c;
	}
	ans = prim(n);
	cout << ans << endl;//ans存最后结果 
	}
	return 0;
}

邻接表法，时间复杂度 o(nlogn+e)

//PTA公路村村通 
#include<iostream>
#include<cstdio>
#include<vector> 
using namespace std;
const int INF = 0x3fffffff;
const int MAXV = 1005;
struct node
{
	int v,dis;
};//v为边的目标顶点，dis为边权 
vector<node> s[MAXV];
int d[MAXV];//d存已标记点到此点的最短距离 
bool vis[MAXV];//vis存是否被标记过 
int prime(int n)
{
	int ans = 0;//边权最小值 
	fill(vis,vis+MAXV,false);
	fill(d, d + MAXV, INF);
	d[1] = 0;//从第一个城镇开始 
	for (int i = 0; i < n; i++)//n个点，循环n次 
	{
		int u = -1, Min = INF;//Min存放最小d[u],u点的d[u]最小 
		for (int j = 1; j <= n; j++)//寻找未访问点中最小d[] 
		{
			if (vis[j] == false && d[j] < Min)
			{
				u = j;
				Min = d[j];
			}
		}
		if (u == -1)return -1;//不连续，无法连成一棵树 
		vis[u] = true;//标记已访问 
		ans += d[u];
		for (int k = 0; k < s[u].size(); k++)//更新与u点连接的最优值 
		{
			int v=s[u][k].v;//通过邻接表直接获得u能到达的顶点v 
			//k未访问&&u为中介点使k离集合更短 
			if (vis[v] == false && s[u][k].dis < d[v])
				d[v] = s[u][k].dis;
		}
	}
	return ans;
}
int main()
{
	int n, m, i, a, b, c, ans;//n代表城镇个数，m代表路径个数 
	while(scanf("%d %d",&n,&m)!=EOF&&n)
	{
		for(i=0;i<MAXV;i++)//清空所有邻接表 
		{
			s[i].clear();
		}
	for (i = 0; i < m; i++)
	{
		node t;
		cin >> a >> b >> c;//输入两个城镇与权值 
		t.v=b;
		t.dis=c;
		s[a].push_back(t);
		t.v=a;
		t.dis=c;
		s[b].push_back(t);
	}
	ans = prime(n);
	cout << ans << endl;//ans存最后结果 
	}
	return 0;
}

kruskal 算法 适用于边少的情况

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
const int MAXN=1005; 
const int N=105; 
struct node
{
	int x, y, z;//x,y代表端点，z权值 
}s[MAXN];
int father[N];//并查集数组 
int findfather(int v)//并查集函数 
{
	if (v == father[v])return v;
	else 
	{
		int f = findfather(father[v]);
		father[v]=f;//压缩路径 
		return f;
	}
}
bool cmp(node a, node b)//权值小的放前面 
{
	return a.z < b.z;
}
int kruskal(int n,int m)//n个顶点，m边数 
{
	int i,num=0,a,b,ans=0;//num存选择的边数，ans存最小权值 
	for (i = 1; i <= n; i++)//并查集初始化 
		father[i] = i;
	sort(s + 1, s + m + 1, cmp);//按边的权值从小到大排序 
	for (i = 1; i <= m; i++)
		{
			a = findfather(s[i].x); b = findfather(s[i].y);
			if(a!=b)//不在一个集合 
			{
				father[b] = a;//合并集合 
				num++;//道路数量相加 
				ans += s[i].z;//权值 
				if (num == n - 1)break;//边数等于顶点减 1时结束 
			}
		}
		if(num!=n-1)return -1;//无法连通时返回-1 
		else return ans;
}
int main()
{
	int m, n, i, sum;
	while (scanf("%d %d", &n,&m)!=EOF && n && m)//n代表城镇个数，m代表路的个数 
	{
		for (i = 1; i <= m; i++)
		{
			scanf("%d %d %d", &s[i].x, &s[i].y, &s[i].z);
		}
		sum=kruskal(n,m);//sum为最小权值 
		printf("%d\n", sum);
	}
	return 0;
}