kruskal最小生成树，poj 1287 Networking 最小生成树 Kruskal Prim

关于Kruskal和Prim在前面已经有详细的解释以及模板了

有关于需要注意的地方，以及在代码中注释出来。

//Kruskal
//用结构体保存起始点以及耗费，然后排序后，根据Kruskal
#include<iostream>
#include<string>
#include<cmath>
#include<ctype.h>
#include<memory.h>
#include<string.h>
#include<algorithm>
#include<map>
#include<iomanip>
#include<set>
#include<list>
#include<vector>
#include<stack>
#include<queue>
#define ll long long int
using namespace std;
const int maxn = 9999999;struct edge
{int u, v, w;
};
bool cmp(edge a, edge b)
{return a.w < b.w;
}int p, r;
edge a[maxn];
int par[maxn];int ans = 0;int find(int x)
{if (par[x] == x)return par[x];return par[x] = find(par[x]);
}
void ini()
{ans = 0;for (int i = 0; i <= p; i++)par[i] = i;
}int main()
{while (cin >> p){if (p == 0)break;cin >> r;ini();for (int i = 0; i < r; i++){int u, v, w;cin >> a[i].u >> a[i].v >> a[i].w;}sort(a, a + r, cmp);for (int i = 0; i < r; i++){int fa = find(a[i].u);int fb = find(a[i].v);if (fa != fb){par[fa] = fb;ans += a[i].w;}}cout << ans << endl;}return 0;
}

//Prim
//#include<iostream>
//#include<string>
//#include<cmath>
//#include<ctype.h>
//#include<memory.h>
//#include<string.h>
//#include<algorithm>
//#include<map>
//#include<iomanip>
//#include<set>
//#include<list>
//#include<vector>
//#include<stack>
//#include<queue>
//#define ll long long int
//using namespace std;
//const int maxn = 9999999;
//
//struct edge
//{
//	int u, v, w;
//};
//bool cmp(edge a, edge b)
//{
//	return a.w < b.w;
//}
//
//int p, r;
//edge a[maxn];
//int par[maxn];
//
//int ans = 0;
//
//int find(int x)
//{
//	if (par[x] == x)
//		return par[x];
//	return par[x] = find(par[x]);
//}
//void ini()
//{
//	ans = 0;
//	for (int i = 0; i <= p; i++)
//		par[i] = i;
//}
//
//int main()
//{
//	while (cin >> p)
//	{
//		if (p == 0)
//			break;
//		cin >> r;
//		ini();
//
//		for (int i = 0; i < r; i++)
//		{
//			int u, v, w;
//			cin >> a[i].u >> a[i].v >> a[i].w;
//		}
//		sort(a, a + r, cmp);
//		for (int i = 0; i < r; i++)
//		{
//			int fa = find(a[i].u);
//			int fb = find(a[i].v);
//			if (fa != fb)
//			{
//				par[fa] = fb;
//				ans += a[i].w;
//			}
//		}
//		cout << ans << endl;
//	}
//	return 0;
//}#include<iostream>
#include<string>
#include<cmath>
#include<ctype.h>
#include<memory.h>
#include<string.h>
#include<algorithm>
#include<map>
#include<iomanip>
#include<set>
#include<list>
#include<vector>
#include<stack>
#include<queue>
#define ll long long int
using namespace std;
const int maxn = 500;
const int INF = 999999;int p, r;
int Map[maxn][maxn];
int dis[maxn];
int vis[maxn];int prim()
{memset(dis, 0, sizeof(dis));memset(vis, 0, sizeof(vis));for (int i = 1; i <= p; i++)dis[i] = Map[1][i];//cout << "dis:";//for (int i = 1; i <= p; i++)//	cout << dis[i] << " ";//cout << endl;for (int i = 1; i <= p; i++){int Min = INF, min_index = -1;for (int j = 1; j <= p; j++){if (dis[j] < Min && !vis[j]){Min = dis[j];min_index = j;}}if (min_index != -1)vis[min_index] = 1;for (int j = 1; j <= p; j++){if (dis[j] > Map[min_index][j] && !vis[j])dis[j] = Map[min_index][j];}}int ans = 0;for (int i = 1; i <= p; i++)ans += dis[i];return ans;
}int main()
{while (cin >> p){if (p == 0)break;cin >> r;//！！！千万不要忘了图的初始化！！！for (int i = 1; i <= p; i++)for (int j = 1; j <= p; j++)Map[i][j] = i == j ? 0 : INF;for (int i = 1; i <= r; i++){int u, v, w;cin >> u >> v >> w;if (Map[u][v] > w)//！！！坑死我了，注意这种情况！！！Map[u][v] = Map[v][u] = w;}/*for (int i = 1; i <= p; i++){for (int j = 1; j <= p; j++)cout << Map[i][j] << " ";cout << endl;}*/cout << prim() << endl;}return 0;
}