(3)映射二分堆实现prim最小生成树模板

//无向图最小生成树,prim算法+映射二分堆,邻接表形式,复杂度O(mlogn)
//返回最小生成树的长度,传入图的大小n和邻接表list
//可更改边权的类型,pre[]返回树的构造,用父结点表示,根节点(第一个)pre值为-1
//必须保证图的连通的!
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <ctime>
using namespace std;

#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)<(b))
struct heap{
 elem_t h[MAXN+1];
 int ind[MAXN+1],map[MAXN+1],n,p,c;
 void init(){n=0;}
 void ins(int i,elem_t e){
  //插入第i个数到堆中
  for (p=++n;p>1&&_cp(e,h[p>>1]);h[map[ind[p]=ind[p>>1]]=p]=h[p>>1],p>>=1);
  h[map[ind[p]=i]=p]=e;
 }
 //从堆中删除第i个数
 int del(int i,elem_t& e){
  i=map[i];if (i<1||i>n) return 0;
  for (e=h[p=i];p>1;h[map[ind[p]=ind[p>>1]]=p]=h[p>>1],p>>=1); 
  for (c=2;c<n&&_cp(h[c+=(c<n-1&&_cp(h[c+1],h[c]))],h[n]);h[map[ind[p]=ind[c]]=p]=h[c],p=c,c<<=1);
  h[map[ind[p]=ind[n]]=p]=h[n];n--;return 1;
 }
 //从堆中删除最小的数，并返回改最小值的原始下标i
 int delmin(int& i,elem_t& e){
  if (n<1) return 0;i=ind[1];
  for (e=h[p=1],c=2;c<n&&_cp(h[c+=(c<n-1&&_cp(h[c+1],h[c]))],h[n]);h[map[ind[p]=ind[c]]=p]=h[c],p=c,c<<=1);
  h[map[ind[p]=ind[n]]=p]=h[n];n--;return 1;
 }
};

elem_t prim(int n,edge_t list[],int* pre){
 heap h;
 elem_t min[MAXN],ret=0,e;
 edge_t* t;
 int v[MAXN],i;
 for (h.init(),i=0;i<n;i++)
  min[i]=(i?inf:0),v[i]=0,pre[i]=-1,h.ins(i,min[i]);
 while (h.delmin(i,e))
  for (v[i]=1,ret+=e,t=list[i].next;t;t=t->next)
   if (!v[t->to]&&t->len<min[t->to])
    pre[t->to]=t->from,h.del(t->to,e),h.ins(t->to,min[t->to]=t->len);
 return ret;
}

//初始化连接表
void Init(edge_t list[],int n)
{
 int i;
 for (i = 0; i < n; i ++)
  list[i].next = NULL;
}
edge_t* FindEnd(edge_t* list)
{
 edge_t* p = list;
 while(p && p->next != NULL)
  p = p->next;
 return p;
}
void CreateLink(edge_t list[],int m,int n)
{
 edge_t* end;
 edge_t* p;
 Init(list,n);
 int i,x,y,z;
 for (i = 0; i < m; i ++)
 {
  scanf("%d%d%d",&x,&y,&z);
  end = FindEnd(list[x].next);//查找链表的最后一个节点
  p = (edge_t*)malloc(sizeof(edge_t));
  p->from = x;
  p->to = y;
  p->len = z;
  p->next = NULL;
  if (!end)
   list[x].next = p;
  else
   end->next = p;
  end = FindEnd(list[y].next);//查找链表的最后一个节点
  p = (edge_t*)malloc(sizeof(edge_t));
  p->from = y;
  p->to = x;
  p->len = z;
  p->next = NULL;
  if (!end)
   list[y].next = p;
  else
   end->next = p;
 }
}
int main(void)
{
 clock_t start,finish;
 start = clock();
 freopen("最小生成树(kruskal邻接表形式).txt","r",stdin);
 edge_t list[MAXN];
 int pre[MAXN];
 int n,m,i;
 scanf("%d%d",&n,&m);
 CreateLink(list,m,n);
 double ans = prim(n,list,pre);
 cout << ans << endl;
 for (i = 1; i < n; i ++)
  cout << pre[i] << "---" << i << endl;
 finish = clock();
 cout << (finish - start) / CLOCKS_PER_SEC << "ms" << endl;
 return 0;
}