解题思路:
还是最小生成树,只需要把已经修建好的路权值改为 0 即可 。
参考代码:
#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] && index != i) dis[i] = Map[index][i]; } return total; } int main() { int paths, pos1, pos2, weigth, finish; while (~scanf("%d", &point) && point) { init(); paths = point*(point - 1) / 2; while (paths--) { scanf("%d%d%d%d", &pos1, &pos2, &weigth, &finish); if (finish == 0) { Map[pos1][pos2] = weigth; Map[pos2][pos1] = weigth; } else { Map[pos1][pos2] = 0; Map[pos2][pos1] = 0; } } cout << prim() << endl; } }
0.0分
0 人评分
C语言训练-求1+2!+3!+...+N!的和 (C语言代码)浏览:789 |
简单的a+b (C语言代码)浏览:631 |
DNA (C语言描述,数据结构)浏览:856 |
C语言程序设计教程(第三版)课后习题9.1 (C语言代码)浏览:681 |
C二级辅导-阶乘数列 (C语言代码)浏览:521 |
大神老白 (C语言代码)浏览:601 |
C语言程序设计教程(第三版)课后习题12.3 (C语言代码)浏览:548 |
敲七 (C++代码)浏览:1056 |
找出最长的字符串来 (C语言代码)浏览:1770 |
C语言程序设计教程(第三版)课后习题5.4 (C语言代码)浏览:459 |