• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

Codeforces 553C Love Triangles 题解

开发技术 开发技术 5小时前 1次浏览

CF553C链接

对于这个题,乍一看没什么思路。但我们可以得到以下结论:

每个三元环的边权和都是 (1)(3)

这里介绍一种判二分图的方法:并查集判二分图

做法是建个新图,把每个点 (i) 拆成 (i)(i + n) 两个点,对原图的每条边 ((i,j)) ,在新图中加入边 ((i, j + n))((i + n, j)),最后对每个 (i) 判断 (i)(i + n) 是否在同一个连通块中就行了(如果都不在同一个连通块中,就是二分图)。

这样做为什么是对的呢?

我们考虑原图有一个奇环,环上的一个点为 (x),那么从新图上的 (x) 出发,经过一系列上下迭代(我们把 (1..n) 画在上面,(n+1..2n) 画在下面),最后会回到 (x + n),那么 (x)(x + n) 就连通了;而偶环则会回到 (x) ,不会出现这种情况。

你是否觉得突然插进来一大通,很莫名其妙?别着急,我们把这个算法与本题建立联系。

先说结论:模仿原算法建图,对于每一条边 ((i,j)) ,若权值为 (0) ,我们加边 ((i,j + n))((i + n, j)) (异侧),否则加边 ((i,j))((i + n, j + n)) (同侧),加完边后按原算法判断。若判断为“二分图”,则原图合法。

简单理解一下,对于一个三元环,把 (4) 种情况验证一下,发现如果边权和为 (1/3) 就判断为“二分图”,为 (0/2) 就不是“二分图”,与我们的需求恰好吻合。

那么深层次的理解呢?或者说这是怎么想出来的?

其实(合法的)原图有一个隐藏的性质:每个环里 (0) 边的数量都是偶数。这完全等价于我们的要求。

这是不是有点像二分图?其实只是把“边”特殊化成了“(0) 边”而已,“(1) 边”不再有影响。那么我们想对 (0) 边做一次二分图判定。(1) 边怎么处理呢?分别合并上下集合就好了,这样“(1) 边”不会改变“上下迭代”中 点的上下位置,自然消除了影响。

不过这题还要求计数,这看上去有点棘手。

都进行到这一步了,我们肯定考虑对新图进行计数,因为一个新图对应了恰好一个原图。

对原图的所有边进行加边操作。由于原图是个完全图,而新图必须保证 (i)(i + n) 不连通,我们可以得到以下性质:

  1. 新图中恰好有两个连通块 (A), (B)
  2. 对于一个点拆出来的两个点,如果一个在 (A) 中,那么另一个一定在 (B) 中。也就是说,(A)(B) 都是在每个位置取了恰好一个点。
  3. (A), (B) 连通块内的边一定连满。

那么一个 (A) 连通块可以唯一确定一个 (B) ,进而可以唯一确定一张图。

考虑 (m = 0) ,没有确定关系的情况。我们先随便找一个 (A) 连通块,这时把 (2 … n) 位置的点翻转一下(即把 (i) 变成 (i + n),把 (i + n) 变成 (i)),该图依然合法。但 (1) 位置的点不能翻转,因为 (A)(B) 是上下对称的,这样会导致重复计数。于是方案数为 (2^{n – 1})

推广到(m > 0) ,有确定关系的情况。我们可以把一个连通块看成一个整体,当成一个点,再按上面的流程计算。显然,设“图的一边”有 (cnt) 个连通块(另一边是对称的),那么方案数为 (2^{cnt-1})

终于做完了!别看我说了这么一大段,其实程序还是很好写的,大部分还是思考的过程。这题虽然 CF 上的难度评分并不高,但技术含量还挺高。


程序员灯塔
转载请注明原文链接:Codeforces 553C Love Triangles 题解
喜欢 (0)