题意

给出n个编号为A~A+n的节点，和某些节点之间的距离，求最小生成树的总权值

思路

裸的Prim算法求最小生成树

算法细节：

最小生成树-Prim算法和Kruskal算法

AC代码

#include <iostream>#include <algorithm>#include <cstdio>#include <cstring>#define mst(a) memset(a, 0, sizeof(a))using namespace std;typedef long long ll;const int INF = 0x3f3f3f3f;const int maxn = 30;ll all;int n;int mc[maxn], d[maxn][maxn], vis[maxn];void init(){all = 0;mst(mc);mst(d);mst(vis);for( int i = 1; i <= maxn; i++ ){for( int j = 1; j <= maxn; j++ ){d[i][j] = i == j ? 0 : INF;}}}ll prim(){for( int i = 1; i <= n; i++ ){mc[i] = INF;vis[i] = 0;}mc[1] = 0;int all = 0;for(;;){int v = -1;for( int i = 1; i <= n; i++ ){if(!vis[i] && (v == -1 || mc[i] < mc[v] ) )v = i;}if( v == -1 ) break;vis[v] = 1;all += mc[v];for( int i = 1; i <= n; i++ )mc[i] = min(mc[i], d[v][i]);}return all;}int main(){int T, nn, cost;char f, t;while( scanf("%d",&T) == 1 && T ){n = T;init();getchar();for( int i = 1; i < T; i++ ){scanf("%c",&f);getchar();scanf("%d",&nn);getchar();//printf("%c %d\n", f, n);while(nn--){scanf("%c",&t);getchar();scanf("%d",&cost);getchar();//printf("%c %d\n", t, cost);int xx = f-'A'+1, yy = t-'A'+1;if( cost < d[xx][yy] ){d[xx][yy] = cost;d[yy][xx] = cost;}}}printf("%lld\n",prim());}return 0;}

如果觉得《HDU 1301 - Jungle Roads( Prim求最小生成树 )》对你有帮助，请点赞、收藏，并留下你的观点哦！