注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

aspe的博客

OI之路阻且长

 
 
 

日志

 
 

最小生成树  

2015-12-20 14:04:26|  分类: 算法&数据结构 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
=========================概念======================
       要讲最小生成树,先了解一下生成树的概念。
       生成树,是一个v个点的连通图,取其中(v-1)条边,并连接所有的顶点,所组成的原图的一个生成树。所以,生成树是无环连通图。
       那么最小生成树,顾名思义,就是所有生成树中,边的权值和最小的一个生成树。
========================实现=======================
有两种算法,其中一种,便是Kruskal算法。

Kruskal算法简述

假设 WN=(V,{E}) 是一个含有 n 个顶点的连通网,则按照克鲁斯卡尔算法构造最小生成树的过程为:先构造一个只含 n 个顶点,而边集为空的子图,若将该子图中各个顶点看成是各棵树上的根结点,则它是一个含有 n 棵树的一个森林。之后,从网的边集 E 中选取一条权值最小的边,若该条边的两个顶点分属不同的树,则将其加入子图,也就是说,将这两个顶点分别所在的两棵树合成一棵树;反之,若该条边的两个顶点已落在同一棵树上,则不可取,而应该取下一条权值最小的边再试之。依次类推,直至森林中只有一棵树,也即子图中含有 n-1条边为止。
说白了,其实就是贪心,在所有边中,选权值尽量小的边组成这棵树,如图:
最小生成树 - 杨鸿飞 - 一个叫杨鸿飞的人的博客
 
首先,我们会发现 点1 到 点2 的这条边权值最小,于是就把这条边作为第一条边,然后 点4 到 点5 的权值为3,就用它做第二条边,如此类推,这样可以确定四条边,可是在找最后一条边时,你会发现,如果是选了4 -> 6 这条边,就会形成环,因此就不能选这条边,于是就选1->4 这条边,这幅图的最小生成树就这样出来了。
终上所述,最小生成树只需两步:
1、按权值从小到大排序
2、依此选取|V|-1条边,注意不能有环。
=======================例题=========================
 题目描述: 
Bessie受雇来到John的农场帮他们建立internet网络。农场有N (2(= N (= 1, 000)牛棚,编号为1. . N. John之前已经勘测过,发现有M (1<=m<= 20, 000) 条可能的连接线路,一条线路是连接某两个牛棚的。每条可能的线路都有一个建 设如C (1<= C <=100,000). John当然想花尽量少的钱,甚至克扣Bessie的 工资。 
Bessie发现了这点,很生气,决定给John捣乱。她要选择)些线路组成网, 但费用却尽可能大。当然网络要能正常工作,也就是任意两个牛棚之间都是相互 可以连通的,并且网络上不能有坏,不然John会很容易发现的。 
请计算组建这种网络最多可能的费用。 
输入文件cowtract. in 
第一行:两个整数N M 
下面M行:每行3个整数A, B, C。表示一个可能的线路要连接A、B两个牛棚, 费用是C。
输出文件cowtract.out 
只一行,一个整数,即花费最大的费用。如果不可能连接通所有牛棚,输出-1。 
输入样例:
5 8
1 2 3
1 3 7
2 3 10
2 4 4
2 5 8
3 4 6
3 5 2
4 5 17
输出样例:
42
注释:
17+8+10+7=42
=======================分析=========================
不就是最小生成树吗,哦,要尽可能大,还不是一样!!!!
程序在此:

#include <cstdio>
#include <algorithm>

using namespace std;

struct Tbian
{ int x,y,v; }; //点x 到 点y 有一条权值为vd的边。

int fa[10100];
Tbian a[200100];

bool _cmp(Tbian x,Tbian y)
{ return x.v>y.v; } //这里是选最大的权值

int ufind(int p) //用并查集来判断是否有环
{
if (p==fa[p]) return p;

fa[p]=ufind(fa[p]);
return fa[p];
}

int main()
{
int k,n;
scanf("%d%d",&k,&n); //k个结点,n条边
for (int i=0; i<n; i++)
scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].v);

sort(a+0,a+n,_cmp); //权值排序
for (int i=1; i<=k; i++) fa[i]=i; //并查集初始化

int sum=0,ans=0;
for (int i=0; i<n; i++)
{
int rootx=ufind(a[i].x); //找祖先
int rooty=ufind(a[i].y); //找祖先

if (sum==k) break; //是否达到k-1条边

if (rootx!=rooty) //不是环
{
fa[rootx]=rooty;
sum++; //边数加一
ans+=a[i].v; //记录权值
}
}
if (sum+1<k) ans=-1;
printf("%d",ans);

return 0;
}


  评论这张
 
阅读(17)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018