1349：【例4-10】最优布线问题

本文主要是介绍1349：【例4-10】最优布线问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

【解题思路】

最小生成树模板题，求最小生成树所有边权加和。
该题输入的是邻接矩阵，因此使用邻接矩阵解决该问题。当然也可以保存为邻接表。

【参考代码】

//示例代码  Prim算法
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;const int N=105;   // 定义常量 N，表示数组大小
int n;
int g[N][N];       // 保存图的邻接矩阵
int minn[N];       // 保存当前已经选定的点到其它点的最小边权值
bool v[N];         // 标记哪些点已经在MST中int main()
{cin>>n;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++) cin>>g[i][j];memset(minn,0x3f,sizeof(minn));    // 将minn数组初始化为最大值minn[1]=0;                         // 从1号结点开始建立MSTmemset(v,true,sizeof(v));         // 将所有结点标记为未被访问过for(int i=1;i<=n;i++){            // 构建n个顶点的MSTint k=0;for(int j=1;j<=n;j++)          // 找到目前离MST最近的点if(v[j]&&(minn[j]<minn[k])) k=j;v[k]=false;                   // 将点k加入MST中for(int j=1;j<=n;j++)          // 更新minn数组if(v[j]&&(g[k][j]<minn[j])) minn[j]=g[k][j];}int ans=0;                        // 计算MST的总边权值for(int i=1;i<=n;i++) ans+=minn[i];cout<<ans;                        // 输出结果return 0;
}

这篇关于1349：【例4-10】最优布线问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---