P3260 [JLOI2014]镜面通道
首先猜结论：如果空气联通的话那么光路就可以穿过。
然后直接转对偶图求最小割即可。
特别注意一下如何判断圆和矩形相交。
- 看矩形的四个角是否在圆内
- 看圆的四个极点是否在矩形内
- 判断是否存在包含关系
当题目的条件非常迷惑的时候，要尝试猜结论，并且猜结论要向着可做的方向去想。
P3749 [六省联考 2017] 寿司餐厅
连边方式如下：
- 每个区间 \([l,r]\) 向 \([l-1,r],[l,r-1]\) 这两个区间连边，表示选了 \([l,r]\) 其子区间必须全选。
- 每个长度为一的区间 \([i,i]\) 权值减去 \(a_i\) ，并且向寿司 \(a_i\) 连边，表示 \(a_i\) 寿司的结点，权值为 \(-mx^2\)
然后就是要求解一个最大权闭合子图的问题。具体方法如下：
首先加上每个正数点权，然后根据点权正负性分类讨论：
- 如果是正的，则向 \(S\) 连边，边权为 \(a\) 。表示如果不选，则要减去这个贡献。
- 否则，向 \(T\) 连边，边权为 \(-a\) 。表示如果选，要加上 \(a\) 这个贡献。
P7737 [NOI2021] 庆典
考虑利用上题目所给的性质。
首先 \(\text{tarjan}\) 缩点，然后拓扑排序缩成外向树，由于题目性质保证，某个点外向树上的父亲是能到达该点的点中拓扑序最大的一个。
接下来考虑每次询问新加的边，将 \(S,T\) 和新边的起点和终点视为关键点，建虚树，再在虚树上加上两条新边变成一个有向图，这样 \(S\rightarrow T\) 路径上的点一定被包含在有向图中，因此从 \(S,T\) 开始 \(\text{bfs}\) 一遍即可。
对于一些存在特殊性质的图，一定要想清楚这个性质有什么用，可以从特殊的图入手，再推广到一般情况。
P8331 [ZJOI2022] 简单题
依然是考虑有 “美好性质” 的图长成什么样。
数所有简单路径的权值之和，可以考虑将每一条路径拆解成若干段（按照割点来拆）。
那么此题关键就是如何求解同一个点双中间的路径方案数。
我们维护两个东西，方案数和权值和，同一个点双最多两种不同走法，在圆方树上维护一个矩阵，特殊考虑一下 \(\text{lca}\) 处即可。
仔细思考题中所给的性质对于解题有什么用！
P8346 「Wdoi-6」最澄澈的空与海
猜性质：每次挑选一个度数为一的点将其删去。
证明略，大胆猜结论吧。
Gym104197 D. Distance Parities
猜结论：如果最短路为奇数，则连一条边。
可以归纳的考虑，有解的情况下这样做一定是正确的，在建完图之后跑一遍 \(\text{floyd}\) 即可。
Gym104197 F. F*** 3-Colorable Graphs
这题手玩一下可以发现，操作次数在 \(2,3\) 之间，那么只需要判断是哪一个即可。
怎么判断呢？手玩发现当且仅当存在四元环时只需操作 \(2\) 次，检查一遍是否存在四元环即可。
四元环计数
用于求解无向图 \(G\) 中存在多少个四元环。
将所有点按照度数从大到小排序，相同的按编号排，记 \(i\) 号点排名为 \(rk_i\) ，对于原图中的每一条边 \((i,j)\) ，如果 \(rk_i<rk_j\) 则在新图中连有向边 \((i,j)\) ，否则连有向边 \((j,i)\) 。
在新图中对四元环进行计数，枚举每个点 \(u\) ，再枚举每个点到达的点
标签：连边,text,讲课,四元,即可,RSY,权值,性质 From： https://www.cnblogs.com/oscaryangzj/p/17169729.html