标签:LCA

Codeforces 733F Drivers Dissatisfaction(最小生成树+LCA)

huangkui 2018年3月16日 No Comments Problem , , ,

题目链接:传送门 Description 给一张n个点m条边的连通图,每条边(ai,bi)有一个权值wi和费用ci,表示这条边每降低1的权值需要ci的花费。现在一共有S费用可以用来降低某些边的权值(可以降到负数),求图中的一棵权值和最小的生成树并输出方案。

LCA总结

huangkui 2017年8月8日 1 Comment Algorithm, 未分类 , , , , , ,

这段时间一直在学习LCA的各种算法,下面就对LCA的各种算法进行一次总结: 问题概述 LCA(最近公共祖先)指的是在一棵树上两个节点的最近的公共祖先(这句话好像跟没说差不多),也就是深度最深的公共祖先。LCA的适用范围非常广,在许多较难的与树有关的题中都会需要用到。因此,掌握求LCA的方法是非常重要的。

Page 1 of 1