ZOJ3526【缩点思想】

一开始做的时候（TLE），A,C,G这三类作为边，然后点和点直接建边搜个环：then time BOOM!

可以发现只属于“A”类的之间都并在一起就好，同理“G”类和“C”类，那么整幅图会变成？

所以我们只需要分析三角的位置，从而就能搞出整个图是否是个环。

一种思路：

直接分类！但是要严谨。。。

1.如果只有以一个“A”类/“G”类/“C”类为交界的，举只有“A”类例子：(num["A"]+num["AG"]+num["AC"]+num["AGC"]==n)，就是yes，同理得G类和C类

2.如果只有以A,G,C其中两个作为交界的，如果只有以A,G的话，那么就是num["C"]==0&&num["AG"]+num["AGC"]>=2，就是yes，同理得相同情况。

3.如果三个都存在的话：num["AG"]?1:0+num["AC"]?1:0+num["GC"]?1:0+num["AGC"]>=3就好了或者(num["AG"]>=2&&num["AC"]>=2)或者(num["AG"]>=2&&num["GC"]>=2)或者(num["AC"]>=2&&num["GC"]>=2)

OK,that's all.

第二种方法：

DFS。

关键还是这幅图，第一种方法判断似乎好像太过思维？

DFS的话注意复杂度，所以要缩小点的数量。

对于A类/C类/G类的话，只需要一个点。

对于AG，GC，AC的话，最多只需要两个，主要就是多了也没用。

对于ACG的话，最多只要三个。

所以整幅图最多1+1+1+2+2+2+3=12，2^12，当然不保险，AG/AC/GC类可以需要3个点？2^15?复杂度还是可以的。

巴特西

ZOJ3526【缩点思想】

最新文章

热门文章