Day 12
欧拉图 二分图
- P10939 骑士放置。
比较经典。
我们注意到对于原图的 \(i + j\) 的奇偶性进行染色，注意到这样的情况一定是合法的。
我们每次考虑对于走“日”字的格子，每一次都进行连边，然后进行二分图最大匹配即可。
复杂度略高，但是这肯定是跑不满的。
实测：复杂度是 \(O(n^3m^3)\) 的做法最慢一个点跑了 131ms，快的飞起。
- P3033 [USACO11NOV] Cow Steeplechase G。
很优美的性质。
我们知道二分图的最小点覆盖=最大匹配=点数-最大独立集。
然后我们把所有相交的线段连起来，然后计算二分图点覆盖，也就是求出这个二分图的最大匹配即可。
强连通分量 双连通分量
-
P2921 [USACO08DEC] Trick or Treat on the Farm G。
我们考虑当然先进行 tarjan 缩点。如果这个点所在的 scc 的大小 \(\ne 1\)，那么说明这个一定在环上，直接找出环即可；如果这个 scc 的大小 \(= 1\)，说明这个点一定不在环上，我们接着走他的 \(nxt_i\) 一直走直到我们找到了位于环上的点即可。
复杂度 \(O(n + m)\)。 -
P5022 [NOIP 2018 提高组] 旅行。
先考虑 \(m = n - 1\) 的情况。很明显，我们从 \(1\) 开始 DFS 即可，每次我们寻找编号最小的点去走即可。
再考虑 \(m = n\) 的情况。我们充分发扬人类智慧，每次枚举环上的一条边，考虑断掉环上这条边，然后再重复 \(m = n - 1\) 的做法即可。
所以，我们进一步简化一下这个东西，我们直接去枚举每一条边，然后再考虑 DFS。如果断掉的这个不是环上的边，那么最后的路径长度一定 \(< n\)，我们直接舍掉即可。