最小生成树-prim算法模板

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define inf 10000000
#define maxn 21
int m,n;
int edge[maxn][maxn],lowcost[maxn],nearvex[maxn];
void prim(int u0)
{
    int i,j;
    int sumweight=0;
    for(i=1; i<=n; i++)
    {
        lowcost[i]=edge[u0][i];
        nearvex[i]=u0;
    }
    nearvex[u0]=-1;
    for(i=1; i<n; i++)
    {
        int min=inf;
        int v=-1;
        for(j=1; j<=n; j++)
        {
            if(nearvex[j]!=-1 && lowcost[j]<min)
            {
                v=j;
                min=lowcost[j];
            }
        }
        if(v!=-1)
        {
            cout<<nearvex[v]<<" "<<v<<" "<<lowcost[v]<<endl;
            nearvex[v]=-1;
            sumweight+=lowcost[v];
            for(j=1; j<=n; j++)
            {
                if(nearvex[j]!=-1 && edge[v][j]<lowcost[j])
                {
                    lowcost[j]=edge[v][j];
                    nearvex[j]=v;
                }
            }
        }
    }
    cout<<"weight of mst is "<<sumweight<<endl;
}
int main()
{
    ios::sync_with_stdio(false);
    freopen("1.txt","r",stdin);
    int i,j,w,u,v;
    cin>>n>>m;
    memset(edge,0,sizeof(edge));
    for(i=1; i<=m; i++)
    {
        cin>>u>>v>>w;
        edge[u][v]=edge[v][u]=w;
    }
    for(i=1; i<=n; i++)
    {
        for(j=1; j<=n; j++)
        {
            if(i==j)
                edge[i][j]=0;
            else if(edge[i][j]==0)
                edge[i][j]=inf;
        }
    }
    prim(1);
    return 0;
}

/*
7 9 
1 2 28
1 6 10
2 3 16
2 7 14
3 4 12
4 5 22
4 7 18
5 6 25
5 7 24

*/