P3366 【模板】最小生成树-Prim

算法原理：

在kruskal算法正确性的基础上，考虑进行优化.
由于kruskal的复杂度为O(mlogm)，在稠密图中表现可能不太好，思考能否利用最短这一性质对复杂度上界进行优化.
联想到dijkstra的性质，可以发现最小生成树在局部也满足这一性质（最小生成树的每一个子树都是一个最小生成树）.
由于任意一点都必然会在最小生成树中，可以从任意一点开始"探索"（类似文明VI中探索地图）.
假设首先选择了1号点，那么对于1号点来说，如果想要拓展自己的大小且花费尽量小，应该选择权值最小的边.
递归进行以上操作，就可以求出整个图的最小生成树.

堆优化：

考虑到在最小生成树的拓展过程中，每个点在被选择时，它所在的"入边"一定是最优选择，而已有的最小生成树可以证明是完美的，而且每个点实际上仅仅是对于其他点的一个"中转站"，所以它的"入边"就不需要再被更新。可以利用这一个性质，结合Dijkstra的堆优化，将"入边"长度作为小根堆的特征值，即可将算法复杂度从 $O(n^2)$ 优化到 $O(nlogm)$

#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int MAXN=5e3+5,MAXM=4e5+5;
struct Edge{
	int from,to,w,nxt;
}e[MAXM];
int head[MAXN],edgeCnt=1;
void addEdge(int u,int v,int w){
	e[++edgeCnt].from=u;
	e[edgeCnt].to=v;
	e[edgeCnt].w=w;
	e[edgeCnt].nxt=head[u];
	head[u]=edgeCnt;
}
struct Node{
	int nowV,nowW;
	bool operator <(Node another)const{
		return nowW>another.nowW;
	}
};
int minw[MAXM];
bool vis[MAXN];
int prim(){
	memset(minw,0x3f,sizeof(minw));
	priority_queue<Node> q;
	q.push(Node{1,0});
	int ans=0;
	while(!q.empty()){
		Node nowNode=q.top();q.pop();
		int v=nowNode.nowV,w=nowNode.nowW;
		if(vis[v])continue;
		vis[v]=1;
		ans+=w;
		for(int i=head[v];i;i=e[i].nxt){
			int nowV=e[i].to;
			if(!vis[nowV]&&e[i].w<minw[nowV]){
				minw[nowV]=e[i].w;
				q.push(Node{nowV,e[i].w});
			}
		}
	}
	return ans;
}
int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		addEdge(u,v,w);
		addEdge(v,u,w);
	}
	int ans=prim();
	printf("%d
",ans);
	return 0;
}