zkx06111's Blog

用LCT解决一类动态图问题

| Comments

给出一个n个点的图,m个操作,一类是加边,一类是删边,还有一类是询问某些信息。可以使用LCT维护删除时间最大生成树。为了支持边权,对于每条边建立一个点。把所有原本点的点权设为INF,边对应的点的点权设为边权,这样就可以支持对边权的询问了。

BZOJ 4025

询问内容:是否为二分图。

加边操作:

  • u, v不连通,直接连接。
  • 连通,并且w(u, v)比u -> v链上的最小边还小
    • u -> v链上有偶数个点,连上的话是偶环,不会产生影响,直接无视。
    • u -> v链上有奇数个点,由于w(u, v)是最小的(意味着最早删除),在它删除之前都不会是二分图,给该边做上标记。
  • 连通,并且w(u, v)比大于等于u -> v链上的最小边
    • 断开最小边,连接u -> v,对于最小边做第二种操作。

删边操作:

  • u, v是树边,直接断开。
  • 不是树边,如果有标记的话清楚标记。

当标记总数为0的时候是二分图,否则不是。

本题代码。

CF Gym 100551 Dynamic Connectivity Contest

A. Connect and Disconnect

加边、删边、询问连通块个数。

初始答案为n。

加边操作:

  • 不连通,直接连接,答案减一
  • 连通,并且w(u, v)比u -> v链上的最小边大
    • 断开最小边,连接u -> v。
  • 连通,并且w(u, v)比小于等于u -> v链上的最小边
    • 直接无视。

删边操作:

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

值得注意的是LCT在查询u, v上最小值的时候不要忘记了splay,另外要保证u < v,以防出现问题。

本题代码。

B. GraphAero

只有加边,问图的桥数量。维护LCT,每条边有是否为桥的标记。

如果不连通,就link,并打上标记。如果连通,就给答案减去链上桥标和,然后清空标记。

值得注意的是打覆盖标记的时候sum也要修改,因为只可能覆盖为0所以我偷了个懒,直接置为0了。还有就是调试信息的输出如果不删的话很耗费时间。

本题代码。

C. Bridges in a Tree

一棵树,每次加一组边,询问桥的数量。和B题一样做,暴力撤销就好了,我没写。

E. Disconnected Graph

给一个图,没有操作,每次询问删除一组边之后是否连通,可以规约到A题,连通块个数为1的时候就是连通的,我没写。

BZOJ 3237

似乎和E题是一模一样,连数据范围都没有变过的。

总结

  • 写了好几遍LCT
  • 学会了LCT的调试技巧?
  • 这类题目的共同点在于在加边u, v时,如果u, v不连通,就只记录它对询问的影响,而不是实际上连接。而对于有删边操作的题目,维护删除时间最大生成树就可以让影响最迟消失的操作留在树上,影响较早消失的记录影响。

Comments

comments powered by Disqus