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