Question

程序设计：有关最小生成树的题 已知N个城市和他们之间的距离，设计一条公路，使之用最小代价连接所有城市

要求：（1）输入为城市之间的距离，输出最短公路里程
（2）要求用克鲁斯卡尔算法实现。
（3）要求有注释说明步骤
还是按K算法吧,拜托了，克鲁斯卡尔算法高手，江湖救急啊！

Answer 1

不太想注释 你又是让用k算法完成 下面又说P算法 我给和P算法 自己看看研究下
#define MAXN 200
#define inf 1000000000
typedef double elem_t;
struct edge_t{
int from,to;
elem_t len;
edge_t* next;
};
#define _cp(a,b) ((a).d<(b).d)
struct heap_t{elem_t d;int v;};
struct heap{
heap_t h[MAXN*MAXN];
105
int n,p,c;
void init(){n=0;}
void ins(heap_t e){
for (p=++n;p>1&&_cp(e,h[p>>1]);h[p]=h[p>>1],p>>=1);
h[p]=e;
}
int del(heap_t& e){
if (!n) return 0;
for
(e=h[p=1],c=2;c<n&&_cp(h[c+=(c<n-1&&_cp(h[c+1],h[c]))],h[n]);h[p]=h[c],p=c,c<<=1);
h[p]=h[n--];return 1;
}
};
elem_t prim(int n,edge_t* list[],int* pre){
heap h;
elem_t min[MAXN],ret=0;
edge_t* t;heap_t e;
int v[MAXN],i;
for (i=0;i<n;i++)
min[i]=inf,v[i]=0,pre[i]=-1;
h.init();e.v=0,e.d=0,h.ins(e);
while (h.del(e))
if (!v[e.v])
for (v[e.v]=1,ret+=e.d,t=list[e.v];t;t=t->next)
if (!v[t->to]&&t->len<min[t->to])
pre[t->to]=t->from,min[e.v=t->to]=e.d=t->len,h.ins(e);
return ret;
}