题意:给定一棵树,有一些点有一些机器人,现在让你删除一些边,使得任意两个机器人都不互达,求最小的权值

思路:首先我们可以确定的是,任意n个机器人,我们删除的边的数量是固定的,一定是n-1条。

那么对于一个固定的数量的话,如果每次取得的边尽量小更优。那怎么保证取得尽量小的边删除满足题意呢?

其实很简单,只要这两条边的两端可以到达两个机器人就可以删除有效。

但是对于每条边,我们都去这样判断的话,复杂度太大,

优化一下,试想,对于两个机器人上的路径,如果我们从大到小的放边,那么最后一条边一定是满足题意的边。

那么我们怎么来判断这个边是不是最后一条边呢?其实很简单,我们在放一条边之后,就把两端加入一个并查集当中,并且根节点涂色,判断最后一个边的两端是否都是机器人都可以。

 

 

poj-1988-Cube Stacking (并查集,双数组维护)

比较好的一个并查集题。 对于每一个根节点,要维护子节点的个数 和 在这个节点之下的箱子数目 用两个数组,在维护 在某个节点之下的箱子数目的时候, 可以在 ...

阅读全文

ZOJ 3641 Information Sharing (并查集)

很明显的并查集,并且比较简单也比较明显。 思路是这样的: 每次到达一个小朋友, 我们都给与他一个编号,并且同时给他的父节点一个 集合 set(他所知道的信...

阅读全文

HDU 3038 How Many Answers Are Wrong(加权并查集)

这个是加权路径的。 以前做的题并查集 仅仅是用来集合的判断而已。 这个题就是加权了。 输入a b v  代表 a ~b的和为 v。越往前的信息越正确。 出现与前面相违...

阅读全文

欢迎留言

*