解题思路:
Prim 是最常用的一种生成树算法,具体算法分析博客上都有很多。实质也是贪心。
参考代码:
#include "iostream" #include "algorithm" #define Inf 0xFFFFFFF; using namespace std; const int mapSize = 101; int Map[mapSize][mapSize]; int dis[mapSize]; /* 当前点对相连点的距离 */ bool Vis[mapSize]; /* 标记数组 */ int point; int prim() { /* - 从第 0 个顶点开始 - */ Vis[0] = true; for (int i = 0; i < point; i++) dis[i] = Map[0][i] != 0 ? Map[0][i] : Inf; int length = 0; /* 因为 N 个点有 N - 1 条边 */ for (int deg = 0; deg < point - 1; deg++) { int index, poi = Inf; for (int i = 0; i < point; i++) if (!Vis[i] && dis[i] < poi) { poi = dis[i]; index = i; } /* 优先选距离最小的 */ length += poi; Vis[index] = true; /* 更新当前已连接点与其他点的最小距离 */ for (int i = 0; i < point; i++) dis[i] = Map[index][i] != 0 ? min(dis[i], Map[index][i]) : dis[i]; } return length; } int main() { cin >> point; for (int i1 = 0; i1 < point; i1++) for (int i2 = 0; i2 < point; i2++) cin >> Map[i1][i2]; cout << prim() << endl; return 0; }
0.0分
0 人评分
C语言程序设计教程(第三版)课后习题5.7 (C语言代码)浏览:685 |
WU-陶陶摘苹果2 (C++代码)浏览:973 |
WU-链表数据求和操作 (C++代码)浏览:1316 |
三角形 (C++代码)记忆化搜索浏览:1234 |
【金明的预算方案】 (C++代码)浏览:843 |
简单的a+b (C语言代码)浏览:577 |
字符逆序 (C语言代码)浏览:643 |
C语言程序设计教程(第三版)课后习题9.1 (C语言代码)浏览:681 |
C语言程序设计教程(第三版)课后习题9.4 (C语言代码)浏览:667 |
矩阵加法 (C语言代码)浏览:1722 |