prim最小生成树算法题poj2485

prim最小生成树算法题poj2485

开始想用kruskal算法自己写写runtime error

#include#include#includeusing namespace std;int a[2510][25100];struct weight{ int a,b; int value; bool operator < (const weight & rhs) const { return value < rhs.value; } bool operator > (const weight & rhs) const { return value > rhs.value; }};int sett[251000];int find2(int x){ while(x != sett[x]) x=sett[x]; return x;}void merge2(int a,int b){ if(a > b) sett[a]=b; else sett[b]=a;}int main(){ int t; scanf("%d",&t); while(t--) { priority_queue , greater > pq; int n; scanf("%d",&n); for(int i=0;i drop;// printf("size=%d n=%d\n",drop.size(),n); while(drop.size() != n-1){// printf("size=%d n=%d\n",drop.size(),n); weight mi = pq-(); pq.pop(); int fx =find2(mi.a); int fy =find2(mi.b); if(fx!=fy){ drop.insert(mi.value); merge2(fx,fy); } }// printf("size%d\n",drop.size() );// for(set::iterator it=drop.begin();it!=drop.end();it++){// printf("dsa\n");// printf("%d ",*it);// } set::iterator it = drop.end(); it--; printf("%d\n",*it ); } return 0;}/*140 1 2 31 0 2 32 2 0 33 3 3 0-1073741819-1073741819*/

然后写的prim算法

#include#include#includeusing namespace std;int cost[510][510];int mincost[510];bool used[510];int n;int prim(){ memset(used,false,sizeof(used)); memset(mincost,65537,sizeof(mincost)); int MAXres=0; mincost[0]=0; while(true){ int v=-1; for(int i=0;iMAXres)MAXres=mincost[v]; for(int i=0;i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。