这个代码还没有测试过，有错误指出
#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
struct cut_edge{
int p, d;
cut_edge(int a, int b){p = a; d = b;}
bool operator < (const cut_edge& o) const{
if(d != o.d)return d > o.d;
return p > o.p;
}
};
priority_queue<cut_edge> pq, pp;//队列中放的是通过割的边，利用有限队列来优化找轻边
int m, n, map[100][100], d[100];
bool judge[100];//在生成树和不在的两个集合 false 为不在 true 为在
void mst_pq(){
int i, j, k, t, w, ans = 0, count = 0, dd;
while(!pq.empty()){
t = pq.top().p;dd = pq.top().d;pq.pop();
if(!judge[t]){//这里可能一个点入队2此，但是不影响计算。
count++;
judge[t] = true;ans += dd;
for(i = 1; i <= n; i++){
if(map[t][i] && !judge[i] && (d[i] == -1 || map[t][i] < d[i])){
d[i] = map[t][i];
pq.push(cut_edge(i, d[i]));
}
}
}
}
printf("count = %d ans = %d\n", count, ans);
}
int main(){
freopen("prime.in", "r", stdin);
freopen("prime.out", "w", stdout);
int i, j, u, v, w;
while(scanf("%d%d", &n, &m) != -1){
memset(judge, 0, sizeof(judge));
memset(map, 0, sizeof(map));
memset(d, -1, sizeof(d));
for(i = 0; i < m; i++){
scanf("%d%d%d", &u, &v, &w);
map[u][v] = map[v][u] = w;
}pq = pp;pq.push(cut_edge(1, 0));
mst_pq();
}
return 0;
}