C++ 实现道路翻新规划问题：最小生成树算法

#include #include #include using namespace std;

const int N = 310, M = 30010; int n, m; int g[N][N]; //邻接矩阵存图 int dist[N]; //最短距离 bool st[N]; //是否已确定最短距离

int prim() { memset(dist, 0x3f, sizeof dist); //初始化所有距离为正无穷 int res = 0; //最小生成树的权值和 for (int i = 0; i < n; i ++ ) //从0号节点开始 { int t = -1; //t记录当前最短距离最小的未确定的节点 for (int j = 0; j < n; j ++ ) //遍历所有节点 if (!st[j] && (t == -1 || dist[t] > dist[j])) //如果j未确定最短距离且j离当前生成树最近 t = j; if (i && dist[t] == 0x3f3f3f3f) return -1; //不连通，无法构成树 if (i) res += dist[t]; //如果不是第一个节点，将最短距离加入结果 st[t] = true; //将最短距离确定 for (int j = 0; j < n; j ++ ) dist[j] = min(dist[j], g[t][j]); //更新所有节点到生成树的最短距离 } return res; }

int main() { cin >> n >> m; memset(g, 0x3f, sizeof g); //初始化邻接矩阵为正无穷 while (m -- ) { int a, b, c; cin >> a >> b >> c; a --, b --; //将节点编号从1改为从0开始 g[a][b] = g[b][a] = min(g[a][b], c); //如果存在多条边，则选长度最短的 } cout << prim() << endl; return 0; }