渝 2024.05.06 流（重庆八中谢自均）
2 CF1630F Making It Bipartite
即选出来最多点，使得不存在一个点既是其他点的倍数又是其他点的因数。
建图。\(i_0\) 表示 \(i\) 为其他点的因数，\(i_1\) 表示倍数。发现一个连边方式：\((i_0,i_1)\) 连一条边（不能同时选），再对于一个 \(x|y\)，连 \((x_1,y_1),(x_0,y_0),(x_1,y_0)\)。容易证明这样连出来求最大独立集就是对的。
但是一般图最大独立集显然不能直接做。考虑一个偏序集（传递闭包）的无向图版本的独立集等于其最长反链，因此如果转成偏序集再套个板子就做完了。
对于上面的连边方式，按照 \(i\) 为第一关键字，\(i_1<i_0\) 为第二关键字排序，发现它就是独立集。最长反链等于，最小链覆盖，偏序集上最小链覆盖等于最小路径覆盖。因此求个最小路径覆盖即可。
还有一个最小割做法，不太懂。
3 [AGC029F] Construction of a tree
jellywen 定理。
考虑必要条件：如果存在一个集合 \(T\) 使得其点集并的大小 \(\le |T|\)，那么一定无解。因此此时必然会连出环。
发现这就充要了。通过构造证明。
令左边为点，右边为点集。点集往左边覆盖的点连边。然后找一个完全匹配，一个匹配表示这个集合中的边的儿子是谁。如果没有匹配根据上面的条件显然无解。
此时左边会剩下一个点，以其为根，然后从它出发开始 dfs。令当前点为 \(u\)，每次找到一个与其有边且没有被 dfs 过的点集，然后走到与当前点集匹配的那个点 \(v\)，连一条 \((u,v)\)，然后再递归 \(v\)。
容易发现如果这么递归完了那就造了一颗树出来了。而如果某个时刻 dfs 不下去了，只有可能是当前 dfs 过的点集 \(|f(S)|= |S|+1\)，而剩下的点满足 \(|f(S)|=|S|\)，恰好就是无解条件。
写个 dinic 即可。
4 [AGC038F] Two Permutations
做过的题。
对于每个位置 \(i\)，其 \(A\) 选 \(0,1\)，\(B\) 选 \(0,1\) 各有贡献。但发现判掉置换环大小为 \(1\) 的情况，只有 \((0,0),(1,1)\) 有贡献。然后就可以最小割了。而判掉是简单的。
5 [ARC161F] Everywhere is Sparser than Whole (Judge)
考虑怎么求最大密度子图。
考虑二分，令当前中点为 \(\lambda\)，则判断即为 \(|E|-|X|\lambda\ge 0\)。这个东西考虑最大权闭合子图，把边拆成点，然后跑一边最大权闭合子图即可。
而对于本问题，如果最大密度子图 \(>D\) 显然不行。否则即判断是否有非空真子图密度等于 \(D\)。
结论：找出点与边的完美匹配，然后定向使得每个点的出度等于 \(D\)，再判断极大强联通分量是否唯一即可。
证明是简单的。
还有比较炫酷的其它做法。