最小生成树----Prim

思路：

1. 任意找一个点
2. 遍历这个点的所有边，并找到未经过点的且权值最小的边，将其累加起来
3. 通过这条边，找到下一个点
4. 重复2和3，直到遍历所有的点

                时间复杂度O(n²)

   Code：

   #include<iostream>
   #include<memory.h>
   #include<cmath>
   using namespace std;
   const int INF=9999999;
   int v[5005];//判断某个点是否被遍历过
   int d[5005];//已经遍历过的点到其余点的距离
   int g[5005][5005],n,m,ans=0;
   int prim(int s)
   {
    memset(v,0,sizeof(v));
    int k;
    for(int i=1;i<=n;i++)
    {
        d[i]=g[s][i];//存在就赋值，不存在就是正无穷
    }
    v[s]=1;//起点已经遍历过
    d[s]=0;//起点到起点的距离为0
    for(int i=1;i<=n-1;i++)
    {
        int minn=INF;//初始化最小值
        for(int j=1;j<=n;j++)
        {
            if(v[j]==0&&minn>d[j])
            {
                minn=d[j];
                k=j;
            }
        }
        v[k]=1;//给遍历过的点打好标记
        d[k]=0;//遍历过的点到本身的距离为0
        ans+=minn;//将最小值累加
        for(int j=1;j<=n;j++)
        {
            if(v[j]==0&&d[j]>g[k][j]) d[j]=g[k][j];//更新已经遍历过的点到其余点的距离
        }
    }
    return ans;
   }
   int main()
   {
    cin>>n>>m;    
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    g[i][j]=INF;
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        cin>>x>>y>>z;
        g[x][y]=g[y][x]=min(z,g[x][y]);
    }
    int t=prim(1);
    if(t==-1) cout<<"orz";
    else cout<<t;
    return 0;
   }