?

题意：给出一个数字n代表邻接矩阵的大小，随后给出邻接矩阵的值。输出最小生成树的权值。

题解：

prime算法的基本解法；

1.选择一个点，然后不停的向其中加入权值最小的边，边的一端在已经生成的部分生成树中，另一端在未生成的生成树中。

2.利用优先队列维护边，将加入的点所包含的边加入到队列中去，随后按照边的权值弹出。

简单理解方法：一个人可以拉很多人，新被拉进来的人，把能拉的人（有边，且未被访问）排队，找最好拉的人拉进来，循环。

注意：

1.如果使用priority_queue(二叉堆)+prime算法，时间复杂度为ElogV

2.直接使用邻接矩阵，复杂度为O(n^2)

3.使用STL 优先队列的时候记得定义排序方法；（见代码：14行）

4.记得清空vector数组

?

Kruskal算法的基本解法：

1.Kruskal算法存的是边。将所有边存起来，然后按照从小到大排序，依次加入两端不再同一集合的边。

2.复杂度为O(ElogE)

3.稀疏图

简单理解方法：几个人抱团，最后在全都拉在一起。

树的特点：边的个数是n-1，所以加入n-1条边即可停止。

?

?

Prime+堆解法——代码：

?

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #define INF 0xffffff using namespace std; struct Edge { int v; int w; Edge(int v_, int w_):v(v_), w(w_){} bool operator < (const Edge &e) const { return w > e.w; } }; typedef vector 
      
        vedge; vector 
       
         g(110); int n; int Prime(vector 
        
          & g) { int i, j, k; vector 
         
           visit(n); vector 
          
            dist(n); priority_queue 
           
             pq; for(i = 0; i < n; i++) { visit[i] = 0; dist[i] = INF; } Edge temp(0, 0); int nOwn = 0; int nWeight = 0; pq.push(Edge(0, 0)); while(nOwn < n && !pq.empty()) { do { temp = pq.top(); pq.pop(); } while(visit[temp.v] == 1 && !pq.empty()); if(visit[temp.v] == 0) { nOwn++; nWeight += temp.w; visit[temp.v] = 1; } for(i = 0 ; i < g[temp.v].size(); i++) { int v = g[temp.v][i].v; if(visit[v] == 0) { int w = g[temp.v][i].w; dist[v] = w; pq.push(Edge(v, w)); } } } if(nOwn < n) { cout << nOwn << n << endl; return -1; } return nWeight; } int main() { int i, j, k; int temp; while(~scanf(%d, &n)) { for(i = 0; i < n; i++) g[i].clear(); for(i = 0; i < n; i++) for(j = 0; j < n; j++) { scanf(%d, &temp); g[i].push_back(Edge(j, temp)); } cout << Prime(g) << endl; } return 0; }
           
          
         
        
       
      
     
    
   
  

Kruscal算法代码：

?

//author: svtter
//

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        const int MAXN = 100000; using namespace std; vector 
       
         root; int n; struct Edge { int i, j, w; Edge(int i_, int j_, int w_):i(i_), j(j_), w(w_){} bool operator < (const Edge &e) const { return w < e.w; } }; void init() { for(int i = 0; i < n; i++) root.push_back(i); } int getRoot(int i) { if(root[i] == i) return i; return root[i] = getRoot(root[i]); } void Merge(int i, int j) { int a, b; a = getRoot(i); b = getRoot(j); if(a == b) return; //a's root is a; root[a] = b; } vector 
        
          g; int Kruskal() { //init the init(); sort(g.begin(),g.end()); //the num of tree's Edges is n-1; // int nEdge = 0; //the weight of whole gtree int nWeight = 0; int i, s, e, w; for(i = 0; i < g.size(); i++) { s = g[i].i; e = g[i].j; w = g[i].w; if(getRoot(s) != getRoot(e)) { Merge(s,e); nWeight += w; nEdge++; } if(nEdge == n-1) break; } return nWeight; } int main() { int i, j, k; while(~scanf(%d, &n)) { g.clear(); root.clear(); for(i = 0; i < n ; i++) for(j = 0; j < n; j++) { scanf(%d, &k); g.push_back(Edge(i, j, k)); } cout << Kruskal() << endl; } return 0; } 
        
       
      
     
    
   
  

?

?