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?复杂度还是可以的。




原文地址:https://www.cnblogs.com/keyboarder-zsq/p/6777397.html