对于最小生成树来说，是找安全边的问题。
贴个kruskal的代码
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
struct e{
int u, v, w;
};
e edge[1000];
bool cmp(e a, e b){
return a.w > b.w;
}
int m, n, f[1000];
int find(int i){//并查集
if(i != f[i])return f[i] = find(f[i]);
return f[i];
}
int main(){
freopen("kruskal.in", "r", stdin);
freopen("kruskal.out", "w", stdout);
int i, j, u, v, w, el, ans, tm;
while(scanf("%d%d", &n, &m) != -1){
el = 0;
for(i = 1; i <= n; i++)f[i] = i;
for(i = 0; i < m; i++){
scanf("%d%d%d", &u, &v, &w);
edge[el].u = u;edge[el].v = v;edge[el++].w = w;
}tm = m;ans = 0;
make_heap(edge, edge + m, cmp);//堆优化
for(i = 0; i < n - 1; tm--){
u = find(edge[0].u);v = find(edge[0].v);
if(u != v){
printf("edge[0].w = %d\n", edge[0].w);
f[u] = v;i++;ans += edge[0].w;
}
pop_heap(edge, edge + tm, cmp);
}
printf("%d\n", ans);
}
return 0;
}