解题思路:
还是最小生成树,只需要把已经修建好的路权值改为 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++代码)(C++库中有qsort函数直接快排,不用码排序代码hhh)浏览:974 |
逆反的01串 (C++代码)(依旧推荐switch)浏览:936 |
点我有惊喜!你懂得!浏览:4107 |
上车人数 (C语言代码)浏览:1178 |
C语言训练-谁家孩子跑最慢* (C语言代码)浏览:1508 |
简单的a+b (C语言代码)浏览:646 |
母牛的故事 (C语言代码)浏览:435 |
DNA (C语言描述,数据结构)浏览:852 |
蛇行矩阵 (C语言代码)浏览:527 |
打印十字图 (C语言代码)浏览:2708 |