摘要： 算法概述：对于一个带权的连通图，其顶点的集合 为V，边的集合为E。定义一个新的集合Vnew={空}，第一步在图中任选一个顶点v加入Vnew，第二步寻找最短的边(u,v),其中u∈Vnew，v∈V-Vnew，其中v加入Vnew，循环执行第二步直到Vnew=V结束。
算法概述：对于一个带权的连通图，其顶点的集合 为V，边的集合为E。定义一个新的集合Vnew={空}，第一步在图中任选一个顶点v加入Vnew，第二步寻找最短的边(u,v),其中u∈Vnew，v∈V-Vnew，其中v加入Vnew，循环执行第二步直到Vnew=V结束。
voidprime(){inti,j;intmin=INF;for(i=1;ilowcost[j]) { min=lowcost[j]; k=j; } } vnew[k]=1;for(j=1;j<=n;i++) {if(!vnew[j]&&map[k][j]
题目大意：n个城市，知道各个城市的距离，建路将n个城市互相可达，路是直线建的，max=各个城市最长的那条路，求所有建路方案中max的最小值。
解题思路：直接prime求最小生成树
代码（已ac）
#include#include#include#defineN 510#defineINF 0x3f3f3f3fusingnamespacestd;int_map[N][N];intVnew[N];intlowcost[N];intprime(intn){inti,j;int_min;intans=-1;for(i=1;i<=n;i++) lowcost[i]=INF; lowcost[1]=0;memset(Vnew,0,sizeof(Vnew));for(i=1;i<=n;i++) {intk; _min=INF;for(j=1;j<=n;j++) {if(!Vnew[j]&&_min>lowcost[j]) { _min=lowcost[j]; k=j; } } ans=max(ans,_min); Vnew[k]=1;for(j=1;j<=n;j++) {if(!Vnew[j]&&lowcost[j]>_map[k][j]) { lowcost[j]=_map[k][j]; } } }returnans;}intmain(void){intT,i,j;intk;scanf("%d",&T);intn;while(T--) {scanf("%d",&n);for(i=1;i<=n;i++)for(j=1;j<=n;j++)scanf("%d",&_map[i][j]); k=prime(n);printf("%d\n",k); }return0;}
版权声明：本文内容由互联网用户自发贡献，版权归作者所有，本社区不拥有所有权，也不承担相关法律责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件至：yqgroup@service.aliyun.com 进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容。
用云栖社区APP，舒服~
网友评论