MemoryGarden's Blog

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

C++博客 首页 新随笔 联系 聚合 管理
  118 Posts :: 11 Stories :: 20 Comments :: 0 Trackbacks
链接 : http://acm.pku.edu.cn/JudgeOnline/problem?id=3625

题意 :  将所有农场链接的最小长度,即最小生成树。但是有的 边已经连接完毕

输入 :

4 1 // 4个点 1个已经连完的边
1 1  //点坐标
3 1
2 3
4 3
1 4  //连接完毕的点地编号


想法 :将连接完毕的点地权值更改为0,克鲁斯 + 并查  或者  将已经连接的点先并入一个集合

核心代码如下 :

1. 将已经连接的点先并入一个集合

1 for(i = 0; i < m; i++){
2             scanf("%d%d"&u, &v);
3             if((u = find(u)) != (v = find(v))){
4                 f[u] = v;
5                 n--;
6             }
7         }


2. 并查集合

int find(int x){
    
if(x != f[x])return f[x] = find(f[x]);
    
return f[x];
}


3. 克鲁斯卡尔 + 并查

 1 tel = el;
 2         make_heap(e, e + el, cmp);
 3         for(i = 0; i < n - 1; tel--){
 4             if((u = find(e[0].u)) != (v = find(e[0].v))){
 5                 f[u] = v;
 6                 sum += e[0].w;
 7                 i++;
 8             }
 9             pop_heap(e, e + tel, cmp);
10         }






posted on 2008-09-05 21:29 memorygarden 阅读(368) 评论(0)  编辑 收藏 引用 所属分类: 报告

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