本文主要是介绍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】最优布线问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
