本文主要是介绍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算法）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
