Prim模板

• 适合稠密图
• 集合U是图G的点集，V是最小生成树的点集。任选U中一点加入V，再从U-V中找一点到V中任意点权值最小，将其加入V，如此反复。
• O（E*logV）
• 代码：

   1 #include <bits/stdc++.h>
   2 int w[105][105],dis[105],f[105],n,s=0;
   3 const int M=2100000;
   4 using namespace std;
   5 void prim(int vi){
   6     for(int i=1;i<=n;i++){
   7         if(w[vi][i]!=0){
   8             dis[i]=w[vi][i];
   9         }
  10         else dis[i]=M;
  11     }
  12     f[vi]=1;
  13     int k,min=0;
  14     for(int i=1;i<=n-1;i++){
  15         min=M;
  16         for(int j=1;j<=n;j++){
  17             if(f[j]==0&&dis[j]<min){
  18                 min=dis[j];
  19                 k=j;
  20             }
  21         }
  22         s=s+min;
  23         f[k]=1;
  24         for(int j=1;j<=n;j++){
  25             if(dis[j]>w[k][j]){
  26                 dis[j]=w[k][j];
  27             }
  28         }
  29     }
  30 }
  31 int main(){
  32     cin>>n;
  33     for(int i=1;i<=n;i++){
  34         for(int j=1;j<=n;j++){
  35             cin>>w[i][j];
  36         }    
  37     }
  38     for(int i=1;i<=n;i++){
  39         for(int j=1;j<=n;j++){
  40             if(w[i][j]==0) w[i][j]=M;
  41         }
  42     }
  43     prim(1);
  44     cout<<s<<endl;
  45     return 0;
  46 }

   

Prim模板

原文：https://www.cnblogs.com/wi1d3on/p/11330984.html