本文主要是介绍HDU 1863(prime)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：点击打开链接
题目大意：给你n个点，m条边，问你为了让每个城市之间都能联通最少需要多少钱。
题目思路：之前用的是kruskal算法写的这题，这里用prime，感觉kruskal简单很多..有点像迪杰斯特拉算法，有一个vis来标记是否走过，一个dis确定目前最短路程。首先输入n,m表示n条边m个房子，然后输入n条边。接着把vis[1]标记为走过，然后dis[i]存1到各点的距离。然后进行一个m-1次的循环。每次循环中，第一步是找出没标记过的点的距离最小的是哪个，并且记录一下最小值，如果最小值是inf，就说明已经不存在满足条件的点，可以直接break并判定无法实现最小生成树。如果可行的话ans+上这个距离。然后对这个点进行标记。接着再遍历一边没有被标记的点，并且更新他们的最短距离。如果m-1次循环能够完成的话，说明能够形成m-1条边，即能够完成最小生成树满足题意，输出ans即可，否则输出？。
以下是代码：
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
#include<map>
using namespace std;
#define inf 0x3f3f3f3f
int map1[105][105],vis[105],dis[105];
int main()
{int n,m,u,v,w;while(~scanf("%d%d",&n,&m)&&n){memset(vis,0,sizeof(vis));memset(map1,inf,sizeof(map1));int ans=0;for(int i=0;i<n;i++){scanf("%d%d%d",&u,&v,&w);if(map1[u][v]>w){map1[u][v]=w;map1[v][u]=w;}}vis[1]=1;int p=1;for(int i=2;i<=m;i++){dis[i]=map1[1][i];}int i;for(i=1;i<m;i++){int min1=inf;for(int j=1;j<=m;j++){if(!vis[j]&&dis[j]<min1){min1=dis[j];p=j;}}if(min1==inf){break;}ans+=min1;vis[p]=1;for(int j=1;j<=m;j++){if(!vis[j]&&map1[p][j]<dis[j]){dis[j]=map1[p][j];}}}if(i==m){printf("%d\n",ans);}else{printf("?\n");}}return 0;
}
这篇关于HDU 1863(prime)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
