最小乘积生成树(BZOJ2395: [Balkan 2011]Timeismoney)

给定一个$n$个点$m$条边的图,一条边有两个值$a$,$b$,求最小花费生成树,定义花费为这$n-1$条边的$a$值和这$n-1$条边的$b$值和。

将一个方案的答案$(\sum a,\sum b)$看作一个二维平面上的点。

则要求的即为最靠近左下的点。

那么开始先求出最靠近$x$轴和$y$轴的点(即按$a$为权值做一遍最小生成树和按$b$做一遍),记为$A$,$B$。

然后要求的便是离$AB$最远的$C$点($solve(A,B)$),可以用叉积来判断。

也就是$\vec{CA}*\vec{CB}$最小,将$(x[i]-Ax,y[i]-Ay)*(x[i]-Bx,y[i]-By)$拆开,可以发现新的权值便为$x[i]*(Ay-By)+y[i]*(Bx-Ax)$,以此再做一遍最小生成树便能求出$C$,求出$C$的同时,与最优答案作比较,将更优的作为答案。

然后递归$solve(A,C),solve(C,B)$。

终止条件为$\vec{CA}*\vec{CB}>=0$ 叉积大于等于$0$,即不存在在$A,B$点左下角的点。

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注