1349：【例4-10】最优布线问题——Prim算法

【题目描述】
学校有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。

分析

1. 此题就是最小生成树的板题，参考acwing的模板即可，这个算法有点像Dijkstra算法，迭代+选一个t，然后更新，只不过prim算法用t更新每个点到集合（生成树）的距离；
2. 如果当前不是第一个点的话，并且dist[t]等于正无穷的话，即当前距离最近的点 t 到集合都是正无穷，说明当前图不连通的，直接return；需要一个i的判断，当i为0，说明为第一个结点，生成树至少要有一个结点，所以不进行累加处理，以及return的判断；
   

#include <bits/stdc++.h>using namespace std;const int N = 105, INF = 0x3f3f3f3f;int n;
int g[N][N];    // 邻接矩阵，存储所有边
int dist[N];    // 存储其他点到当前最小生成树的距离
int st[N];      // 存储每个点是否已经在生成树中// 如果图不连通，则返回INF(值是0x3f3f3f3f), 否则返回最小生成树的树边权重之和
int prim() {memset(dist, INF, sizeof dist);int res = 0;//n次迭代for (int i = 0; i < n; ++i) {int t = -1;for (int j = 1; j <= n; ++j) {if (!st[j] && (t == -1 || dist[t] > dist[j]))t = j;}//如果当前不是第一个点的话，并且dist[t]等于正无穷的话，即当前距离最近的点到集合都是正无穷，说明当前图不连通的if (i && dist[t] == INF)return INF;//累加权值（当i为0，说明为第一个结点，生成树至少要有一个结点）if (i)res += dist[t];st[t] = 1;//用t更新每个点到集合（生成树）的距离for (int j = 1; j <= n; ++j) {//区分dijkstra：dist[j] = min(dist[j], dist[t] + g[t][j]);// g[j][t]为当前j到生成树t的距离dist[j] = min(dist[j], g[j][t]);}}return res;
}int main() {cin.tie(0);memset(g, INF, sizeof g);cin >> n;for (int i = 1; i <= n; ++i) {for (int j = 1; j <= n; ++j) {cin >> g[i][j];}}int ans = prim();cout << ans;return 0;
}