大家好,又见面了,我是你们的朋友全栈君。
bzoj2395[Balkan 2011]Timeismoney最小乘积生成树
两个属性
考虑化成二维平面的点
每一个方案对应二维平面上的一个点(t,c)
答案一定在下凸壳上
先找到t,c的最小生成树点A,B这两者一定在凸包上
连线AB,找下面距离AB最远点C
即CA CB叉积最小(注意带符号)
推式子,改边权即可。
然后递归处理其余两边的点
凸包上的点不会太多。。。O(能过)
坐标转化思想注意
有的时候坐标可以:求凸包,斜率优化,扫描线。。。
转载于:https://www.cnblogs.com/Miracevin/p/10209669.html
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/107107.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...