题目描述
最小生成树问题是实际生产生活中十分重要的一类问题。假设需要在n个城市之间建立通信联络网，则连通n个城市只需要n-1条线路。这时，自然需要考虑这样一个问题，即如何在最节省经费的前提下建立这个通信网。
可以用连通网来表示n个城市以及n个城市之间可能设置的通信线路，其中网的顶点表示城市，边表示两个城市之间的线路，赋于边的权值表示相应的代价。对于n个顶点的连通网可以建立许多不同的生成树，每一棵生成树都可以是一个通信网。现在，需要选择一棵生成树，使总的耗费最小。这个问题就是构造连通网的最小代价生成树，简称最小生成树。一棵生成树的代价就是树上各边的代价之和。
而在常用的最小生成树构造算法中，普里姆（Prim）算法是一种非常常用的算法。
在本题中，读入一个无向图的邻接矩阵（即数组表示），建立无向图并按照以上描述中的算法建立最小生成树，并输出最小生成树的代价。
输入
输入的第一行包含一个正整数n，表示图中共有n个顶点。其中n不超过50。
以后的n行中每行有n个用空格隔开的整数，对于第i行的第j个整数，如果不为0，则表示第i个顶点和第j个顶点有直接连接且代价为相应的值，0表示没有直接连接。当i和j相等的时候，保证对应的整数为0。
输入保证邻接矩阵为对称矩阵，即输入的图一定是无向图，且保证图中只有一个连通分量。
输出
只有一个整数，即最小生成树的总代价。请注意行尾输出换行。
样例输入
0 2 4 0
2 0 3 5
4 3 0 1
0 5 1 0
样例输出
6
提示
在本题中，需要掌握图的深度优先遍历的方法，并需要掌握无向图的连通性问题的本质。通过求出无向图的连通分量和对应的生成树，应该能够对图的连通性建立更加直观和清晰的概念。
代码：
#include<bits/stdc++.h>
using namespace std;
const int N = 55;
struct Graph{
int vnum;
int arcs[N][N];
};
const int inf = 1e9;
bool vis[N];//访问标记数组,表示当前结点是否在集合内
void Prim(Graph &G){
memset(vis,0,sizeof(vis));//初始化访问数组
int n = G.vnum;//n为结点个数
int ans=0;//用于存储最小生成树的总代价 //千万不要忘记变量初始化！！！！！！！
vector<int>dis(n);//用于存储点到集合的距离
vis[0] = 1;//将第一个结点标记为已访问
for(int i=1;i<n;++i) dis[i]=G.arcs[0][i];//初始化点到集合的距离，初始时，集合中只有0点，所以所有点到0的距离即为初始dis[i]的值
for(int k=1;k<n;++k){//共进行n-1次循环，因为要找n-1条边
int m = inf;//表示权值最大值
int j = 0;//j用于记录当前离集合距离最短的点的下标
for(int i=1;i<n;++i){//找点到集合距离最短的点
if(vis[i]==0&&dis[i]<m){//如果当前扫描到的结点未被访问过且当前结点到集合的距离（权值） 不为无穷大（即当前结点到集合有边）
m = dis[i];//更新当前点到集合的最短距离
j = i;//当前距离集合距离最短的点的下标
}
}//for循环结束，找到了当前距离集合最近的点
if(j==0){//如果j=0（即当前图没有生成树），则没找到
puts("图不连通");
return;
}
ans +=m;//统计最小权值
vis[j]=1;//j进入集合
for(int i=1;i<n;++i){//更新邻接点到集合的距离
if(G.arcs[j][i]<inf&&!vis[i]){
dis[i]=min(dis[i],G.arcs[j][i]);//选一个最短的
}
}
}
printf("%d\n",ans);
}
int main(void){
Graph G;
scanf("%d",&G.vnum);//输入结点个数
for(int i=0;i<G.vnum;++i){
for(int j=0;j<G.vnum;++j){
scanf("%d",&G.arcs[i][j]);
if(G.arcs[i][j]==0) G.arcs[i][j]=inf;//将0全部转换为inf
}
}
Prim(G);
return 0;
}
本文含有隐藏内容，请 开通VIP 后查看