MemoryGarden's Blog

努力 -----------大能猫

C++博客 首页 新随笔 联系 聚合 管理
  118 Posts :: 11 Stories :: 20 Comments :: 0 Trackbacks
对于最小生成树来说,是找安全边的问题。

贴个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;
}


posted on 2009-10-06 23:31 memorygarden 阅读(214) 评论(0)  编辑 收藏 引用 所属分类: 图论

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理