最大生成树（Greedy Algorithm）_dengjinghan的博客-程序员秘密

技术标签：图论

最近在各大OJ上经常看到最大生成树的题，学了这么长时间算法了，生成树问题也见了不少。众所周知（当然，是学算法的），生成树是一个很经典的问题，但引起模型比较简单，生成树问题一般不是很难（这里小小的装一下），常见的模型就那么几个，最基本的就是最小生成树。众所周知（又是众所周知），最小生成树的两个算法就是kruskal和prim；但最大生成树又怎么解呢，这个问题困扰了我很长时间，直到今天我在网上看到了一篇文章，我才恍然大悟。
下面是那篇文章的链接，如果不想看我的理解或想看完原版再看我的文章的话，你的鼠标就可以点击它了：
[参考原文  最大生成树](http://blog.sina.com.cn/s/blog_605f5b4f01013szs.html)

下面是我自己的理解：
在那篇文章中，作者说最大生成树也是用贪心做（就像kruskal和prim一样），其实在刚看到最大生成树时我就想到用贪心了，不过我当时在想像最小生成树一样，先从大到小排序，然后贪心。不过这显然是不可以的，因为两点之间的路径还可以经过其他的点，这样可能会一条边只连接着两个更优。
真正的最大生成树其实是间接地进行最小生成树，设所有边的权值之和为s，然后将每条边的权值更新为s-ai，ai为原边权。然后求最小生成树，所得边的集合就是原图的解。
为什么这样可以呢？设sa为最小生成树的权值和，则sa = (N-1)*s - x，x为选出来的ai的和，因为（N-1）*s是固定值，所以sa最小时，x最大；

本文链接：https://blog.csdn.net/dengjinghan/article/details/49593909

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

Onhand Qty(Tree) Diagnostics Scripts R12_papaya的博客-程序员秘密

10 04:46:12] INV_QUANTITY_TREE_PVT: Node Rev Lot Sub Loc Lpn qoh rqoh qr qs att atr qs_adj1 Rsv Marked[20-SEP-10 04:46:12] INV_QUANTITY_TREE_PVT: ----------------------------------------------------

OpenSSL密码库算法笔记——第3.1.2章模减_bn_mod_sub 大整数内存释放_艾米的爸爸的博客-程序员秘密

模减的思想与模加类似：先做大整数的减法，然后再调用BN_nnmod做模运算。───────────────────────────────────────int BN_mod_sub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m)功能：模减运算输入： a，b，m【模数】输出： r ←...

linux shell 如何获取命令参数_onionnmmn的博客-程序员秘密

例：输出ps : shell 参数获取写法 $1 等效于 ${1}

简单的登录、注册以及带有验证码功能_y306984159的博客-程序员秘密

echarts柱状图与轴不重叠_用Echarts做堆积的柱状图，当横轴为“time”类型时，都是从0开始显示，而不是叠加，为什么会这样？..._weixin_39792519的博客-程序员秘密

echarts为Echarts2，在自己页面上做没有效果，因此在其例子http://echarts.baidu.com/echa…的基础上改为下面的代码(横轴改为时间类型)var stime='2016-01-01',etime='2016-09-01',time=new Date('2016-04-01');option = {tooltip : {trigger: 'axis',axisPoi...

Ha1cyon-CTF 芜湖_YenKoc的博客-程序员秘密

感觉自己还是很欠缺的，尤其是C++的逆向，对stl的不熟悉，直接误导我静态分析了。。。然后这种题和平常不同的是没有任何混淆和flag验证，需要的是耐心的分析，在过程中，找到线索，这题还考了base64的隐写，2333，开拓了思维，感谢出题师傅，也和出题师傅交流了很久，这种题十分适合动调，注意中间过程，尤其是寄存器和堆栈的变化。拖入ida，找到了主函数，整体逻辑很清晰。重点说下几个函数，这个函...