本文主要是介绍P3366 【模板】最小生成树-Prim，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
算法原理：
- 在kruskal算法正确性的基础上，考虑进行优化.
- 由于kruskal的复杂度为O(mlogm)，在稠密图中表现可能不太好，思考能否利用最短这一性质对复杂度上界进行优化.
- 联想到dijkstra的性质，可以发现最小生成树在局部也满足这一性质（最小生成树的每一个子树都是一个最小生成树）.
- 由于任意一点都必然会在最小生成树中，可以从任意一点开始"探索"（类似文明VI中探索地图）.
- 假设首先选择了1号点，那么对于1号点来说，如果想要拓展自己的大小且花费尽量小，应该选择权值最小的边.
- 递归进行以上操作，就可以求出整个图的最小生成树.
堆优化：
- 考虑到在最小生成树的拓展过程中，每个点在被选择时，它所在的"入边"一定是最优选择，而已有的最小生成树可以证明是完美的，而且每个点实际上仅仅是对于其他点的一个"中转站"，所以它的"入边"就不需要再被更新。可以利用这一个性质，结合Dijkstra的堆优化，将"入边"长度作为小根堆的特征值，即可将算法复杂度从
优化到
题目地址
#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\n",ans);return 0;
}
这篇关于P3366 【模板】最小生成树-Prim的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
