登录 | 注册

优就业C++教程-最小乘积生成树

首页 > 程序开发 > C/C++ 2016-08-05 10:58:42 浏览次 共 条评论

收藏赞(分享

所谓最小乘积生成树,即对于一个无向连通图的每一条边均有两个权值xi,yi,在图中找一颗生成树,使得Σxi*Σyi取最小值。

直接处理问题较为棘手,但每条边的权值可以描述为一个二元组(xi,yi),这也就不难想到将生成树转化为平面内的点,x代表Σxi,y代表Σyi(注意这里的xi,yi指的是在生成树中的边的权值),那么问题就变成了在平面内找一个点使得x*y最小,那么显然这个点是在下凸壳上的。

因此可以首先找出两个一定在凸包上的点,例如A(minx,y),B(miny,x),在直线AB下方找一个在凸包上且x*y最小的点。

于是可以每次找距离直线AB最远的点,有两种求法,令找到的那个点为C,如果利用叉乘,即使向量CB叉乘向量CA最大,因为我们考虑的是向量的模长,可以让向量CA叉乘向量CB(虽然模长是负的,但并没有什么关系,当然也可以最大化这个值,只不过一个是最小生成树,一个是最大生成树而已),然后最小化这个值即可。

2S=(B.x-A.x)(C.y-B.y)-(B.y-A.y)(C.x-A.x)省略常数后就变成了B.x*C.y-A.x*C.y-B.y*C.x+A.y*C.x。

因为只需要求Σxi,Σyi,因此只需要求出点的坐标,并不要考虑面积,所以将每条边的yi=yi*(B.x-A.x),xi=xi*(A.y-B.y),以(xi+yi)为关键字排序kruskal()就行了。

然后递归处理,直到叉积大于等于0退出(此时AB下方一定没有点)

也可以利用点到直线的距离公式|Ax0+By0+C|/(√(A2+B2)),省略常数且保证B<=0,那么若点在直线下方,则Ax+By+C>0。

因此可以省略绝对值符号,再省略常数,即使Ax0+By0最大,因此xi=xi*A,yi=yi*B,将(xi+yi)为关键字排序作最大生成树即可,还是按叉积判断(理应也可以看C.x*A+C.y*B<=0就退出,然而狂WA不止。。。。并不知道这是为什么。。。。)

然后这是一道裸题,就可以愉快地切掉了。

免责声明:本文来源于博客园,由网友提供或网络搜集,仅供个人研究、交流学习使用,不涉及商业盈利目的。如有版权问题,请联系本站管理员予以更改或删除。优知网会定期发布程序开发相关趋势文章,包括 PHP Android IOS Java C/C++ 软件测试 大数据 Linux 等领域,敬请关注!

分享到
人收藏5 收藏
 
我要评价
 
 

咨询中心

优就业微信扫一扫
微信扫一扫

400-650-7353

加入官方微博