Prim模板

堆优化后的算法
O（ElogV）

#include<bits/stdc++.h>
#define ll long long
using namespace std;

const int maxn=2e5+15;
const int mxn=5e3+15;
struct node
{
    int t;int d;
    bool operator < (const node &a) const
    {
        return d>a.d;
    }
};
int n,m;
int vis[mxn];
vector <node> e[mxn];
priority_queue <node> q;
inline int read()
{
    char ch=getchar();
    int s=0,f=1;
    while (!(ch>='0'&&ch<='9')) {if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9') {s=(s<<3)+(s<<1)+ch-'0';ch=getchar();}
    return s*f;
}
ll prim()
{
    ll ans=0;
    int cnt=0;
    q.push((node){1,0});
    while (!q.empty()&&cnt<=n)
    {
        node k=q.top();q.pop();
        if (vis[k.t]) continue;
        vis[k.t]=1;
        ans+=k.d;
        cnt++;
        for (int i=0;i<e[k.t].size();i++)
        if (!vis[e[k.t][i].t]){
            q.push((node){e[k.t][i].t,e[k.t][i].d});
        }
    }
    return ans;
}
int main()
{
    n=read();m=read();
    for (int i=1;i<=m;i++)
    {
        int x=read(),y=read(),z=read();
        e[x].push_back((node){y,z});e[y].push_back((node){x,z});
    }
    printf("%lld",prim());
    return 0;
}

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

代码：

 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 }