HDU 1162 Eddy's picture 最小生成树 Prim模板 发表于 2017-05-15 | 分类于 算法 | 阅读次数: 字数统计: 426 字 算法链接:http://acm.hdu.edu.cn/showproblem.php?pid=1162 题意&题解裸的最小生成树,先计算出各个点的距离,跑一遍Prime。以此题记录Prime算法模板 代码1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980#include<cstdio>#include<cstring>#include<cstdlib>#include<cmath>#include<ctime>#include<iostream>#include<queue>#include<algorithm>using namespace std;#define INF 0x3f3f3f3fconst int maxn=205;const int maxm=2005;double cost[maxn][maxn];double mincost[maxn]; //到已经确定的点的最短距离bool used[maxn];int V;double xx[maxn],yy[maxn];double get_dist(int a,int b){ return sqrt((xx[a]-xx[b])*(xx[a]-xx[b])+(yy[a]-yy[b])*(yy[a]-yy[b]));}void build(){ for(int i=1;i<=V;i++) scanf("%lf %lf",&xx[i],&yy[i]); for(int i=1;i<=V;i++) for(int j=1;j<=V;j++) { cost[i][j]=cost[j][i]=get_dist(i,j); }}double prim(){ fill(mincost,mincost+V+1,INF); //注意建图方式 fill(used,used+V+1,false); //注意建图方式 mincost[1]=0; //注意建图方式 //used[0]=true; 不在这里初始初始化 double res=0; while(true) { int v=-1; for(int i=1;i<=V;i++) //注意建图组织方式 { //在这里对收录一号元素,因为要遍历一号元素的相邻结点 if(!used[i]&&((v==-1)||mincost[i]<mincost[v]))v=i; } if(v==-1) break; used[v]=true; res+=mincost[v]; //cout<<v<<" "<<res<<endl; for(int i=1;i<=V;i++) //注意建图方式 mincost[i]=min(mincost[i],cost[v][i]); //不判断是否相邻 } return res;}void solve(){ while(scanf("%d",&V)!=EOF) { build(); double ans=prim(); printf("%.2lf\n",ans); }}int main(){ freopen("input.txt","r",stdin); solve(); return 0;} 赏 WeChat Pay Alipay 本文作者: Sixzeroo 本文链接: https://www.liuin.cn/2017/05/15/HDU-1162-Eddy-s-picture-最小生成树-Prim模板/ 发布时间: 2017年5月15日 - 09时05分 最后更新: 2019年1月6日 - 14时01分 版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 3.0 许可协议。转载请注明出处!