图论总结
今天大佬讲课就是不一样
大概总结一下今天学到的毒瘤
首先就是一大堆环
一般环好像就几种思路吧
-
首先就是生成树
-
然后就考虑一下如果是有向无环，就可以搞一下拓扑
-
其实还有就是特殊的一些环的题目，往往要考虑复杂环
-
再一个就是考虑特殊的三元环，可能和前后继有关
然后就是图的特殊理解了
往往需要考虑在线的做法更难想到，例如CF767C
还有就是这个结论
有向完全图有一个性质：没有自环，没有二元环，若存在环，则一定存在三元环。
证明的话，就是考虑存在一个多元环，一定会像分多边形一样，分成多个三角形（三元环）
发现在最短路上魔改真的是我的弱点
其他的题就是降智吧，没啥特别的意义感觉
再一个就是复杂度分析真的很烦