简单的代码。。
时间复杂度为O((n + m)logn)
大部分情况下还是跑不过kruskal的，慎用。
1 #include <cstdio> 2 #include <queue> 3 #include <cstring> 4 #define heap pair<int, int> 5 6 using namespace std; 7 8 int n, m, cnt, ans; 9 int head[5001], to[400001], next[400001], val[400001]; 10 bool vis[5001]; 11 priority_queue <heap, vector <heap>, greater <heap> > q; 12 13 inline void add(int x, int y, int z) 14 { 15 to[cnt] = y; 16 val[cnt] = z; 17 next[cnt] = head[x]; 18 head[x] = cnt++; 19 } 20 21 inline void queue_prim() 22 { 23 int i, u, v, tot = n; 24 heap x; 25 q.push(make_pair(0, 1)); 26 while(!q.empty() && tot) 27 { 28 x = q.top(); 29 q.pop(); 30 u = x.second; 31 if(vis[u]) continue; 32 vis[u] = 1; 33 ans += x.first; 34 tot--; 35 for(i = head[u]; i != -1; i = next[i]) 36 { 37 v = to[i]; 38 if(!vis[v]) q.push(make_pair(val[i], v)); 39 } 40 } 41 } 42 43 int main() 44 { 45 int i, x, y, z; 46 memset(head, -1, sizeof(head)); 47 scanf("%d %d", &n, &m); 48 for(i = 1; i <= m; i++) 49 { 50 scanf("%d %d %d", &x, &y, &z); 51 add(x, y, z); 52 add(y, x, z); 53 } 54 queue_prim(); 55 printf("%d", ans); 56 return 0; 57 }