解题思路:
最小生成树。
输入数据量大的话用 cin 就显得很慢,scanf 就快很多了,或者手动解除同步。
参考代码:
#include <bits/stdc++.h> #define Inf 0x3F3F3F3F using namespace std; int Map[102][102]; int dis[102]; bool vis[102]; int point; void init() { memset(Map, 0x3F, sizeof(Map)); memset(vis, false, sizeof(vis)); for (int i = 1; i <= point; i++) Map[i][i] = 0; } int prim() { for (int i = 1; i <= point; i++) dis[i] = Map[1][i]; vis[1] = true; int total = 0; for (int i = 1; i < point; i++) { int Min = Inf, index; for (int pos = 1; pos <= point; pos++) if (!vis[pos] && Min > dis[pos]) { Min = dis[pos]; index = pos; } total += dis[index]; vis[index] = true; for (int i = 1; i <= point; i++) if (dis[i] > Map[index][i] && Map[index][i] != 0) dis[i] = Map[index][i]; } return total; } int main() { int paths, pos1, pos2, weig; while (~scanf("%d", &point) && point) { init(); paths = point*(point - 1) / 2; while (paths--) { scanf("%d%d%d", &pos1, &pos2, &weig); Map[pos1][pos2] = weig; Map[pos2][pos1] = weig; } cout << prim() << endl; } }
0.0分
0 人评分
2003年秋浙江省计算机等级考试二级C 编程题(1) (C语言代码)浏览:603 |
C语言训练-阶乘和数* (C语言代码)-------- 呆板写法浏览:1345 |
C语言程序设计教程(第三版)课后习题1.6 (C语言代码)浏览:654 |
C语言程序设计教程(第三版)课后习题1.6 (C语言代码)浏览:536 |
蚂蚁感冒 (C语言代码)浏览:1319 |
Pascal三角 (C语言代码)浏览:641 |
C语言程序设计教程(第三版)课后习题12.1 (C语言代码)浏览:641 |
简单的a+b (C语言代码)浏览:628 |
简单的a+b (C语言代码)浏览:531 |
C语言程序设计教程(第三版)课后习题8.5 (C语言代码)浏览:549 |