CF1105E - Helping Hiasat

可以发现,在两个 1 操作之间的人中最多满足一个。我们可以两两连边,这样问题就转换为最大独立集问题,按照套路此时我们作补图,将最大独立集转换为求补图最大团

最大团的常用算法是 Bron Kerbosch ,我们甚至不需要很强的优化剪枝就可以过掉这题。

用 tarjan 遍历整个图,如果某个点是割点,当且仅当以下两种情况

  1. 当前点是根节点,且当前节点出发独立的联通分量至少有两个
  2. 当前点不是根节点,且当前节点出发的独立分量能回溯到的最早的点在当前节点之后

转换过来就是下面两个条件

  1. u == root && child >= 2
  2. u != root && low[v] >= dfn[u]

其他与 tarjan 算法无异。

可以看做一张有n个节点的图,每个节点有且仅有一条向外连接的边(可以连自己)。那么图中只可能是环与链的组合。而且链的终点是环,进入环后就不会从环中出去,故一个链只可能接一个环,一个环只可能被一或多的链接。

故我们可以把整个分隔为一个个的环,并把接到他们的链找出来。

  • 环内节点的答案 = 环的长度;
  • 环外节点的答案 = 环的长度 + 当前节点到环的距离。

几趟 $O(n)$ 的搜索就可以搞定问题!

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×