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...