首页 / 算法 / 洛谷1265prim算法求最小生成树
洛谷1265prim算法求最小生成树
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了洛谷1265prim算法求最小生成树,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2519字,纯文字阅读大概需要4分钟。
内容图文
![洛谷1265prim算法求最小生成树](/upload/InfoBanner/zyjiaocheng/637/c38e24f587aa4e3095eb701b60f153d8.jpg)
题目链接:https://www.luogu.com.cn/problem/P1265
最小生成树的prim算法跟dijkstra算法非常像,就是将点分成两个集合,一个是已经在生成树中的点的集合,一个是还未加入生成树的点的集合。最初选择一个点进入集合{V1},然后从{V}-{V1}点集中选择到{V1}距离最短的点进入点集{V1},这样迭代地操作下去,直到所有的点都已经访问过。其实这就是一个合并连通分量的过程,每次都选择最小的合并代价进行合并,最终由局部最优解得出全局最优解,至于最小生成树的算法的正确性的严格的证明,请见我的另一篇博客,本人菜鸡一枚,有错误还请指正。
代码如下:
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef unsigned int ui; 4 typedef long long ll; 5 typedef unsigned long long ull; 6 #define pf printf 7 #define mem(a,b) memset(a,b,sizeof(a)) 8 #define prime1 1e9+7 9 #define prime2 1e9+9 10 #define pi 3.14159265 11 #define lson l,mid,rt<<1 12 #define rson mid+1,r,rt<<1|1 13 #define scand(x) scanf("%llf",&x) 14 #define f(i,a,b) for(int i=a;i<=b;i++) 15 #define scan(a) scanf("%d",&a) 16 #define mp(a,b) make_pair((a),(b)) 17 #define P pair<int,int> 18 #define dbg(args) cout<<#args<<":"<<args<<endl; 19 #define inf 0x3f3f3f3f 20 const int maxn=1e6+10; 21 int n,m,t; 22 inline int read(){ 23 int ans=0,w=1; 24 char ch=getchar(); 25 while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();} 26 while(isdigit(ch))ans=(ans<<3)+(ans<<1)+ch-'0',ch=getchar(); 27 return ans*w; 28 } 29 struct node{ 30 int x,y; 31 }e[maxn]; 32 double ans; 33 double d[maxn]; 34 int vis[maxn]; 35 double dis(int i,int j) 36 { 37 int x=e[i].x,y=e[i].y,xx=e[j].x,yy=e[j].y; 38 return sqrt((double)(x-xx)*(x-xx)+(double)(y-yy)*(y-yy)); 39 } 40 void prim() 41 { 42 mem(vis,0); 43 f(i,1,n)d[i]=inf; 44 d[1]=0; 45 f(i,1,n)//迭代次数,为n次 46 { 47 int pos; 48 double tmp; 49 tmp=inf,pos=-1; 50 f(j,1,n) 51 { 52 if(!vis[j]&&d[j]<tmp) 53 { 54 tmp=d[j],pos=j;//找出到点集最小的边的长度和编号 55 } 56 } 57 if(tmp==inf) return; 58 vis[pos]=1; 59 ans+=tmp; 60 f(j,1,n)//刚标记过的点对剩余的点进行松弛操作 61 { 62 if(!vis[j]) 63 d[j]=min(d[j],dis(pos,j)); 64 } 65 } 66 } 67 int main() 68 { 69 //freopen("input.txt","r",stdin); 70 //freopen("output.txt","w",stdout); 71 std::ios::sync_with_stdio(false); 72 n=read(); 73 f(i,1,n) 74 { 75 e[i].x=read(),e[i].y=read(); 76 } 77 prim(); 78 pf("%.2lf",ans); 79 }
内容总结
以上是互联网集市为您收集整理的洛谷1265prim算法求最小生成树全部内容,希望文章能够帮你解决洛谷1265prim算法求最小生成树所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。