关键词：
Preface
对于形如给定一些边，其边权为xi和yi，构造一个生成树，使得
我们称这棵树，为最小乘积生成树。我们可以考虑，沿用最小生成树的思想，把这种新颖的最小生成树做对。
Content
算法简介
其实就是利用树形结合的思想，将点弄到平面直角坐标系上，使之明了，转化问题，求出最优解。
算法应用
应对类似的裸题，直接裸奔
算法核心
我们将sigma(xi)看成横坐标，sigma(yi)看成纵坐标，在坐标系中绘制出来。并在x,y轴作垂线，构成一个正方形
我们要求一种方案xy=k最小，也就是这个正方形最小，也就是反比例函数（等面积线）y=k/x最接近坐标轴（k最小，即y最小）
显然可以知道，把所有点列出来，构建一个下凸壳，最优的点(x,y)必定在下凸壳上。
如下图，如果一个点不在凸包上，那么以这个点作矩阵，显然面积比以被圈圈起来的点作矩阵优，这更显然吧？
网上大都用分治求解
固定凸包上最接近x轴与y轴的两个节点，即求离x轴，y轴最近的点（分别以x，y为关键字作最小生成树即可，所得x，y必定最小）。
寻找一个点C，使得C离AB最远，也就是△ABC面积最大，想要用C来更新答案。这个点C是目前最优的。
如何找点C？我们用向量来考虑。可能觉得比较奇妙，说不出个之所以然，但是过程严谨，是没有错的，多悟一下，睡前想一想，第二天就懂了。
向量AB=（B.x-A.x，B.y-A.y）
向量AC=（C.x-A.x，C.y-A.y）
根据向量定义，得出S△ABC=AB
最小乘积生成树bzoj2395timeismoney
http://www.lydsy.com/JudgeOnline/problem.php?id=2395考虑在二维坐标系上一种生成树方案\((cost,time)\)对应一个点答案一定是在下凸包上的一段我们考虑如何找到这个下凸包首先找到两个初始点\(a,b\)分别对应以\(cost\),\(time\)为最优然后我们可... 查看详情
hdu5697刷题计划dp+最小乘积生成树
...http://blog.csdn.net/u013849646/article/details/51524748注：这里用的最小乘积生成树的思想，和dp结合 每次找满足条件的最优的点 查看详情
蓝桥杯——算法提高最小方差生成树
...边权为(es[i].cost-sum*1.0/(N-1))2，即方差公式的分子，然后跑最小生成树算法，同时记录边的原来的权值和，如果求出的“最小方差”生成树的边权值和为sum，那么，用这个"最小方差"去更新答案。二、复杂度分析 时间复... 查看详情
bzoj2395timeismoney
最小乘积生成树。本质上是把生成树作为平面上的点，那么答案一定在下凸壳上。递归求解。#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#definemaxv250#definemaxe10050#defineinf1000000007usingnamespaces 查看详情
[编程题]lk[152.乘积最大子数组-二维动态规划](代码片段)
[编程题]lk152.乘积最大子数组-二维动态规划题目输入输出方法1：使用一个二维的dp来表示当前节点的最大值和最小值情况思想：?每个dp[i]位置用两个维度表示值信息，dp[i][0]表示目前的最大值情况,dp[i][1]表示目前的最小值情况如... 查看详情
次小生成树
次小生成树次小生成树我们已经熟知了求最小生成树的方法，用kruskal,prim算法都可以搞那么我们如何求次小生成树呢？这里次小生成树的定义是边权和严格大于最小生成树的边权和最小的生成树求解方法次小生成树嘛，肯定和最... 查看详情
试题复习
...了代码，后面刷题是要花时间写代码了。HNOI2014T1：类似最小乘积生成树，KM算法建出凸包。T2：虚树DP，想到这个应该就不难了。T3：语文题。技巧：取log后用加法代替乘法。T4：字符串hash，模拟题。T5：复杂度玄学的题目，考场... 查看详情
严格次小生成树(代码片段)
...@滑翔翼我过了！！！感动中国！！！111.前置算法kruskal求最小生成树倍增求LCA2.定义次小生成树，顾名思义，边权值和大于等于最小生成树的边权和且边权和最小的生成树而严格次小生成树，就是边权值和严格大于最小生成树的... 查看详情
总结(严格)次小生成树(代码片段)
前言首先需要了解什么是最小生成树,还要知道什么是倍增(求Lca).上面的东西如果了解了,就可以开始进入学习的路途了!!1算法框架1.1整体思路用不是最小生成树上的边去更新答案.1.2具体维护对于每一个倍增跳上去的,要维护两个... 查看详情
bzoj3571[hnoi2014]画框（最小乘积完美匹配）
... 使得suma*sumb最小。 【题解】 把方案看成一个二维点，x=sum(a),y=sum(b) 答案一定在下凸壳上，找到l,r两个点，l是x最小的，r是y最小的 查看详情
次小生成树
...链接：http://acm.timus.ru/problem.aspx?space=1&num=1416题意：求最小生成树和次小生成树，有则输出权值，没有则输出-1题目保证没有重边次小生成树prim求法：次小生成树可由最小生成树换掉一条边求得先用prim算出最小生成树prime过程... 查看详情
poj1679theuniquemst（次小生成树）
题目链接：http://poj.org/problem?id=1679题目大意：求出最小生成树，并且判断最小生成树是否唯一，即次小生成树的路径和是否等于最小生成树，是则输出路径和，反之输出"Notunique!".解题思路：求次小生成树，我看的是O（n^2）的算... 查看详情
次小生成树算法
...对于一个无向带边权连通图G(V,E)，我们一定能从中提取出最小生成树，那么对于次小生成树该如何获取？记图G中有效生成树集合为Z，而T为G的中的总权重最小的生成树，那么G{T}中总权重最小的树就是次小生成树。 我们不妨... 查看详情
poj-1679theuniquemst（次小生成树）(代码片段)
...679TheUniqueMST题目大意：题目给了一个无向图，判断该图的最小生成树是否唯一。分析：要求出无向图的次小生成树，若次小生成树的权值和最小生成树权值一样，则最小生成树不唯一，否则唯一。求次小生成树：首先需要求出最... 查看详情
次小生成树(代码片段)
...(n-1)条边并使所有点相连，所得到的一棵树即为生成树。最小生成树：如果还没有接触过生成树的同学，欢迎戳->最小生成树详解次小生成树：次小生成树顾名思义，就是边权之和次小的一棵生成树。有严格次小生成树与非严... 查看详情
次小生成树(代码片段)
1/*2最小生成树唯一吗，求出次小生成树3枚举每个非最小生成树里面的边，4加上该边后一定会形成环5最小生成树+该边-最小生成树在环中的最长边6*/7/*8#include<cstdio>9#include<iostream>10#include<algorithm>11#include<cstring>12... 查看详情
洛谷p4180模板严格次小生成树[bjwc2010]次小生成树
严格次小生成树模板算法流程：先用克鲁斯卡尔求最小生成树，然后给这个最小生成树树剖一下，维护边权转点权，维护最大值和严格次大值。然后枚举没有被选入最小生成树的边，在最小生成树上查一下这条边的两端点的路径... 查看详情
次最小生成树模版
...从生成树中取出的第二小的生成树。我们在前面已经说过最小生成树的概念及代码实现了，所以接下来要说的次小生成树应该比较简单理解了。求次小生成树的两种方法1：首先求出最小生成树T，然后枚举最小生成树上的边，计... 查看详情