题目链接：https://www.luogu.org/problemnew/show/P3366

思路：

求最小生成树的模板题，求MST有两种算法——Prim、Kruskal。

两者区别：Prim在稠密图中比Kruskal优，在稀疏图中比Kruskal劣。Prim是以更新过的节点的连边找最小值，Kruskal是直接将边排序。

两者其实都是运用贪心的思路

我使用的Prim算法（邻接表实现），head是表头结点数组，a是表结点数组，len记录未加入生成树的结点到生成树的最小距离，vis用来记录结点是否加入生成树。

使用邻接表的原因是邻接矩阵虽然耗空间小，但它只能表示边的信息，而不能表示点，所以还需要O(n)的枚举复杂度或比邻接表更多的内存来存储与边相关的信息，

所以使用邻接表的效率更高。

1 #include
     
       2 #define R register int 3 using namespace std; 4  5 typedef pair
      
        PII; 6 struct node{ 7     int v,w,next; 8 }a[400005];                //表结点 9 10 int n,m,k,cnt,sum,x,y,z;11 int head[5005],len[5005],vis[5005];12 priority_queue
       
        
         ,greater
         
           > pq;13 14 void add(int u,int v,int w){15     a[++k].v=v;16     a[k].w=w;17     a[k].next=head[u];18     head[u]=k;19 }20 21 void prim(){22     len[1]=0;23     pq.push(make_pair(0,1));24     while(!pq.empty()&&cnt