A28830. 最优布线问题
填空题
困难
知识点
题目描述
最优布线问题
题目描述
学校有n台计算机，为了方便数据传输，现要将它们用数据线连接起来。两台计算机被连接是指它们有数据线连接。由于计算机所处的位置不同，因此不同的两台计算机的连接费用往往是不同的。
当然，如果将任意两台计算机都用数据线连接，费用将是相当庞大的。为了节省费用，我们采用数据的间接传输手段，即一台计算机可以间接的通过若干台计算机（作为中转）来实现与另一台计算机的连接。
现在由你负责连接这些计算机，任务是使任意两台计算机都连通（不管是直接的或间接的）。
输入
第一行为整数n（2≤n≤100），表示计算机的数目。此后的n行，每行n个整数。第x+1行y列的整数表示直接连接第x台计算机和第y台计算机的费用。
输出
一个整数，表示最小的连接费用。
输入样例
3
0 1 2
1 0 1
2 1 0输出样例
2提示
注：表示连接1和2，2和3，费用为2。
参考答案
#include<bits/stdc++.h>
using namespace std;
#define N 105
int n, m, sum, dis[N], edge[N][N];//sum：最小生成树边权加和 edge：邻接矩阵 dis[i]：顶点i到已经确定的顶点中的最小距离
bool vis[N];//vis[i]：顶点i是否已经被确定
void prim()
{
memset(dis, 0x3f, sizeof(dis));
dis[1] = 0;
for(int k = 1; k <= n; ++k)
{
int u = 0;
for(int i = 1; i <= n; ++i)
if(vis[i] == false && (u == 0 || dis[i] < dis[u]))
u = i;
vis[u] = true;
sum += dis[u];//顶点u到已经确定的顶点的最短的边的长度是dis[u]，把这条边加入最小生成树，最小生成树的边权值增加dis[u]
for(int v = 1; v <= n; ++v)
if(edge[u][v] && vis[v] == false && dis[v] > edge[u][v])
dis[v] = edge[u][v];
}
}
int main()
{
cin >> n;
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n; ++j)
cin >> edge[i][j];
prim();
cout << sum;
return 0;
}答案解析
最小生成树模板题，求最小生成树所有边权加和。
该题输入的是邻接矩阵，因此使用邻接矩阵解决该问题。当然也可以保存为邻接表。
上一题
下一题