题目描述

Prim算法求最小生成树（边的正负无关）

朴素版算法：类似于Dijstra算法
（每次先找到t，（不在集合中，且距离最小的点），找到之后用经过t的路径长度来更新距离，然后把t加入集合中，集合中是已经确定了最短路的点

第一次在n个点中选，第二次在n-1个点中选。。。）

初始化距离为 正无穷，然后n次迭代
第一次是随便找点，因为都是正无穷，接下来找的点是与上一个点距离最小的点

每次都要在n个点中选

for(i=0;i<n;i++)
{
    （1）找到不在集合当中的距离最小的点（集合中为在当前连通块中的所有点）
    （2）用t更新其他点到集合的距离：这个点连向集合中的其他边，在这些边中找到距离最小的边
    （3）把t加到集合当中（st[t]=true）
}

C++ 代码

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=510,INF=0x3f3f3f3f;

int n,m;
int g[N][N];
int dist[N];
bool st[N];

int prim()
{
    memset(dist,0x3f,sizeof dist);

    int res=0;  //最小生成树中所有边的长度之和
    for(int i=0;i<n;i++)   //n次迭代
    {
        int t=-1;
        for(int j=1;j<=n;j++)   //找到集合外最小距离的点
        {
            if(!st[j]&&(t==-1||dist[t]>dist[j]))
            t=j;
        }

        if(i&&dist[t]==INF) return INF;  //如果不是第一个点，当前最近的点到该点的距离是正无穷，即不连通
        if(i) res+=dist[t];  //只要不是第一条边,,

        for(int j=1;j<=n;j++)
        {
            dist[j]=min(dist[j],g[t][j]);   //先累加再更新，更新其他点到集合的距离，不是起点到其他点的距离。防止自环权重为负的情况
        }

        st[t]=true;
    }
    return res;
}
int main()
{
    cin>>n>>m;

    memset(g,0x3f,sizeof g);   //初始化为正无穷

    while(m--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        g[a][b]=g[b][a]=min(g[a][b],c);   //没有重边
    }

    int t=prim();

    if(t==INF)cout<<"impossible"<<endl;//所有点不连通则没有生成树
    else
    cout<<t<<endl;
    return 0;
}