RT

Prim算法主要应用于建立最小生成树（MST），同理的还有Kruskal算法。

思想

Prim算法主要应用了“蓝白点”的思想。即蓝点的未进树的节点，白点为已经进树的节点。

1.标记起点（如无明确的起点，任意点都可以）为白点。

2.将下一个离树最近的蓝点（也就是，与目前的白点距离最近的节点）标记为白点，同时不断更新距离（代码中有详细的描述），直至所有蓝点都标记成白点。

Tips

1.为什么任意点都可以呢？

因为，最小生成树需要把所有的节点都并进来，所以任意点都可以。一般以节点1为起点。

2.为什么把当前离树最近的蓝点并进来就行呢？

自己想想叭（滑稽.jpg）

具体见代码

Code

#include<iostream>
#include<cstdio>
using namespace std;  //标准开头
const int N=5001;  //N等于节点数
int n,m;  //n——节点数，m——边数
int mint[N];  //mint[i]——节点i与树的距离
bool vis[N];  //true——为白点，false——为蓝点
bool f[N][N];  //f[i][j]==true——i与j联通，否则不连
int map[N][N];  //邻接矩阵存边
int u,r,w;  //u,r——节点，w的权值
int ans;  //权值和
void init()  //初始化
{
	for(int i=1;i<=n;i++){
		mint[i]=0x3fff;
		vis[i]=false;
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			map[i][j]=0x3fff;
		}
	}
	return ;
}
int main()
{
	cin>>n>>m;
	init();
	for(int i=1;i<=m;i++){
		cin>>u>>r>>w;
		map[u][r]=map[r][u]=min(map[u][r],w);
		f[u][r]=f[r][u]=true;
	}
	mint[1]=0;  //如此赋值，就可使节点1为起点，还不影响结果
	for(int i=1;i<=n;i++){
		int k,maxn=0x3fff;
		for(int j=1;j<=n;j++){  //寻找下一个离树最近的节点
			if(!vis[j]&&maxn>mint[j]){
				k=j;
				maxn=mint[j];
			}
		}
		vis[k]=true;
		if(maxn==0x3fff) break;
		ans+=mint[k];
		for(int j=1;j<=n;j++){  //更新距离
			if(f[k][j]&&mint[j]>map[k][j]) mint[j]=map[k][j];
		}
	}
	cout<<ans;
	return 0;
}

Prim的大体轮廓，但是还得具体情况具体分析

相关题目

P3366【模板】最小生成树