LuoguBZOJ分析$\mathrm{2-SAT}$ 。首先把环抽出来，那么还会剩下很多边。考虑两条有交点的边（这里的 $(1,4)$ 和 $(2,5)$ ）：显然只能一条不变（放在环里面），一条从外面绕一下（放在环外面）。于是就可以上 $\mathrm{2-SAT}$ 了。对于两条有交点的边 $i$ 和 $j$ ，连以下 $4$ 条边：$i\to j+m$ ，表示 $i$ 在里面 $j$...
LuoguBZOJ分析首先将平面图转成对偶图。考虑怎么找到一个平面区域。首先把双向边转成两条单向边，这样每条边都属于一个区域。然后将以每个点为起点的边按极角排序。对于每条边$(u,v)$，在以$t$为起点的边中找到$(v,u)$，排序后它的上一条边就是当前区域的下一条边。这样一直到区域闭合，就找完了一个平面区域。建好对偶图之后，找到任意一颗以无界域为根的生成树。（无界域指面积无限的部分）然后...
LuoguBZOJ分析显然，左上一片$0$，右下一片$1$是最好的。要找出最小的分界线，就是求最小割的板子。然后数据范围很大，$\texttt{Dinic}$过不了？？？发现原图是平面图，转为对偶图求最短路即可。然后这个输入是真的毒瘤代码//It is made by M_sea #include <algorithm> #include <iostream> #in...