用LCT解一类动态图的问题

用LCT解一类动态图的问题

很显然,学过了LCT,大家一定都会用LCT来维护动态树结构了

那么,遇到图问题的时候,是不是也能用lct来解决呢?

解决图问题的时候,我们必须要仍然维护一棵树的形态,否则,lct是做不动的

那么下面来看几道题目


代码戳这里


密码: s5qx

1、Codeforces gym 100551A

x y 增加x、y的边

x y 去掉x、y的边

? 询问图中的联通块数量

显然,没操作前,答案是n

考虑加边

不连通,直接连接,答案减一

连通,并且(u, v)的删除时间比u -> v链上的最早删除时间边大,断开最小边,连接u -> v。

连通,并且(u, v)的删除时间小于等于u -> v链上的最早删除时间边,直接无视。

删边操作

如果u, v是树边

断开u, v,答案加一。因为当前边是已经加入的边里面删除时间最迟的,能够连接u, v的其他边要么已经被删除,要么还没被加入,所以可以放心地答案加一。

u, v不是树边,无视就好,对答案没有影响

2、Codeforces gym 100551B

首先要知道图论中桥的定义:删掉它之后,图必然会分裂为两个或两个以上的子图

那么,这道题目的处理方法就显得比较简单了

因为只有加边,我们对于每一次加边

如果x,y不连通,那么我要要在边上打上标记

如果x,y本来就联通,那么我们要减去x,y链上的所有标记,然后将标记清0

清0的时候,类似rev的方式,打延迟标记即可

3、Codeforces gym 100551E

给出一张图,每次询问删去一组边,询问是否仍为连通图

对于每组询问,前面为删除操作,后面为加入操作(还原),中间在加一个询问操作

然后就规约成了A....直接刚

bzoj3237与这道题目一模一样,甚至连数据范围都一样........

相关推荐

PT站种子制作发布新手全攻略
365bet指定开户网址

PT站种子制作发布新手全攻略

📅 10-10 👁️ 4947
韩剧TV如何缓存视频
best365提现多久到账

韩剧TV如何缓存视频

📅 06-28 👁️ 9306
《星露谷物语》莉亚住处介绍
best365提现多久到账

《星露谷物语》莉亚住处介绍

📅 07-28 👁️ 4375
十二星座谁最会撒娇
365bet指定开户网址

十二星座谁最会撒娇

📅 08-27 👁️ 1405
世界杯32强巡礼之哥伦比亚
bat365手机版app

世界杯32强巡礼之哥伦比亚

📅 06-28 👁️ 2617
中国历史上谥号最长的皇帝是谁?
365bet指定开户网址

中国历史上谥号最长的皇帝是谁?

📅 08-18 👁️ 1236
飓风行动
bat365手机版app

飓风行动

📅 10-15 👁️ 8271
小咖秀闪退怎么回事?小咖秀打不开情况的解决方法介绍
传奇手游开服一条龙价格是多少?如何计算成本?
best365提现多久到账

传奇手游开服一条龙价格是多少?如何计算成本?

📅 09-12 👁️ 7590