首页 > 代码库 > 【HDU3371】Connect the Cities（MST基础题）

【HDU3371】Connect the Cities（MST基础题）

2024-07-13 20:26:19   213人阅读

注意输入的数据分别是做什么的就好。还有，以下代码用C++交可以过，而且是500+ms，但是用g++就会TLE，很奇怪。

 

 1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 #include <cstdlib> 5 #include <cmath> 6 #include <cctype> 7 #include <algorithm> 8 #include <numeric> 9 #include <limits.h>10 11 #define typec int12 using namespace std;13 14 const typec inf = 0xffff;15 const int V = 505;16 int vis[V]; typec lowc[V];17 int Map[V][V];18 19 typec prim (typec cost[][V], int n) {20     int i, j, p;21     typec minc, res = 0;22     memset(vis, 0, sizeof(vis));23     vis[0] = 1;24     for (i = 1; i < n; ++ i) lowc[i] = cost[0][i];25     for (i = 1; i < n; ++ i) {26         minc = inf;27         p = -1;28         for (j = 0; j < n; ++ j) {29             if (0 == vis[j] && minc > lowc[j]) {30                 minc = lowc[j];31                 p = j;32             }33         }34         if (inf == minc) return -1;35         res += minc;36         vis[p] = 1;37         for (j = 0; j < n; ++ j) {38             if (0 == vis[j] && lowc[j] > cost[p][j]) {39                 lowc[j] = cost[p][j];40             }41         }42     }43     return res;44 }45 46 47 int main () {48     int n, road_n, union_n, T;49     scanf("%d", &T);50     while (T--) {51         scanf("%d%d%d", &n, &road_n, &union_n);52         //cout << "road_n : "  << road_n << endl;53         for (int i = 0; i < V; ++ i) {54             for (int j = 0; j < V; ++ j) {55                 if (i == j) Map[i][j] = 0;56                 else Map[i][j] = inf;57             }58         }59 60         for (int i = 0; i < road_n; ++ i) {61             int x, y, w;62             scanf("%d%d%d", &x, &y, &w);63             Map[x - 1][y - 1] = Map[y - 1][x - 1] = min(Map[x - 1][y - 1], w);64 65         }66         /*67         for (int i = 0 ; i < n; ++ i) {68             for (int j = 0; j < n; ++ j) {69                 cout << Map[i][j] << "\t";70             }71             cout << endl;72         }73         */74         for (int i = 0; i < union_n; ++ i) {75             int xx, xx_n, last;76             scanf("%d", &xx_n);77             for (int j = 0; j < xx_n; ++ j) {78                 scanf("%d", &xx);79                 if (!j) {80                     last = xx;81                     continue;82                 } else {83                     Map[xx - 1][last - 1] = Map[last - 1][xx - 1] = 0;84                     last = xx;85                 }86             }87         }88 89         printf("%d\n", prim(Map, n));90     }91     return 0;92 }


联系
我们