HDU1863---最小生成树（prim算法）

本文主要是介绍HDU1863---最小生成树（prim算法），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

/*最小生成树基本算法HDU 1863*/
# include<iostream>
# include<algorithm>

using namespace std;

const int N=205;
const int INF=1000000000;
int g[N][N];
int dis[N],n,m;
bool flag[N];
int Prim()
{

    int mincost=0;

    for(int i=1;i<=n;i++)
    {

        flag[i]=0;//首先对其标记数组进行全部初始化为0，也就表明此时的集合中没有一个元素

        dis[i]=INF;//对距离数组都进行初始化为无穷大，也就是表明此时顶点到任何点的距离都为无穷大

    }

    for(int i=2;i<=n;i++)

        dis[i]=g[1][i];//把顶点为编号1到邻近的点的距离存在dis数组中

    flag[1]=1;dis[1]=0;//把第一个点放入集合中（flag[1]=1;），表示此时集合中只有顶点1一个元素，dis[1]=0,表示顶点到本身的距离为0；

    for(int t=1;t<n;t++)
    {

        int mindis=INF,idx=-1;//定义一个赋初值为无穷大的变量，为了就是比较出最短的距离，用idx变量标记下标

        for(int i=1;i<=n;i++)

            if(!flag[i]&&mindis>dis[i])//!flag[i]表示把没有加入集合元素的点进行比较，而已经加入集合的点就不能；

            {mindis=dis[i];idx=i;}//表示把其中最小的距离找到，并把其最小距离的下标，赋给idx

        if(idx==-1) return -1;//表示如果没有以上条件的，idx的原值不变还是-1，所以就返回-1；

        mincost+=dis[idx];//dis[idx]存放的都是符合条件的最短的距离，然后进行累加，最终mincost得到的将是最短距离的总和，也是最少的花费

        flag[idx]=1;//把符合条件的点放入集合中，也就是更新点

        for(int i=1;i<=n;i++)

        if(!flag[i])//把还没有放入集合的点，进行接下来比较

            if(dis[i]>g[idx][i])//表示从那个刚更新的点的整个集合为起点开始，接着找出最短距离的点，直到全部都找完为止

             dis[i]=g[idx][i];//并把最短距离存下来。
    }
    return mincost;
}
int main()
{
    while(cin>>m>>n)
    {

        if(m==0) break;

        for(int i=1;i<=n;i++)

            for(int j=1;j<=n;j++)

            g[i][j]=INF;

        while(m--)
        {

            int u,v,w;

            cin>>u>>v>>w;

            g[u][v]=min(g[u][v],w);

        }

   int mincost=Prim();

   if(mincost==-1) cout<<"?"<<endl;

   else cout<<mincost<<endl;

    }
    return 0;
}

这篇关于HDU1863---最小生成树（prim算法）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---