首页 > 代码库 > 【HDU1102】Constructing Roads(MST基础题)
【HDU1102】Constructing Roads(MST基础题)
最小生成树水题。prim一次AC
1 #include <iostream> 2 #include <cstring> 3 #include <cstdlib> 4 #include <cstdio> 5 #include <cctype> 6 #include <cmath> 7 #include <algorithm> 8 #include <numeric> 9 10 #define typec int11 using namespace std;12 13 const int V = 105;14 const int inf = 0xffff;15 int vis[V]; typec lowc[V];16 int Map[105][105];17 18 typec prim (typec cost[][V], int n) {19 int i, j, p;20 typec minc, res = 0;21 memset(vis, 0, sizeof(vis));22 vis[0] = 1;23 for (i = 1; i < n; ++ i) lowc[i] = cost[0][i];24 for (i = 1; i < n; ++ i) {25 minc = inf; p = -1;26 for (j = 0; j < n; ++ j) {27 if (0 == vis[j] && minc > lowc[j]) {28 minc = lowc[j]; p = j;29 }30 }31 if (inf == minc) return -1;32 res += minc; vis[p] = 1;33 for (j = 0; j < n; ++ j) {34 if (0 == vis[j] && lowc[j] > cost[p][j]) {35 lowc[j] = cost[p][j];36 }37 }38 }39 return res;40 }41 42 int main () {43 //cout << inf <<endl;44 int n;45 while (cin >> n) {46 for (int i = 0 ; i < n; ++ i) {47 for (int j = 0 ; j < n; ++ j) {48 scanf("%d", &Map[i][j]);49 }50 }51 int ok_line; cin >> ok_line;52 for (int i = 0; i < ok_line; ++ i) {53 int s, e;54 scanf("%d%d", &s, &e);55 Map[s - 1][e - 1] = Map[e - 1][s - 1] = 0;56 }57 cout << prim(Map, n) << endl;58 }59 return 0;60 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。