[NOI2014]魔法森林

题目链接:[NOI2014]魔法森林

一看就会想到最小生成树

不过有个区别: 每条边有两个权值

这就说明我们在按照其中一个权值排序时(不妨为a

还是会出现修改边的情况

修改边?LCT资瓷这种操作

但LCT不是维护点权的么?

【蒟蒻才不会说在这里卡了好久

边改点:

如是 我们把每条边新建个点就好了……

然后按照a从小到大排序边并插入

如果对于一条边 u,v已经联通了

那么判断 u,v之间b最大的边Edge1 与 当前边Edge2 的b 哪个大

当前小就把Edge1切掉

或许您会质疑这样的话Edge2的a会比Edge1的a大啊

但我们既然走到Edge2 说明1和n还不连通 还有a更大的边在后面

附赠:点改边【蒟蒻自推

 

原文地址:https://www.cnblogs.com/hjmmm/p/9272341.html