这道题感觉挺厉害的，记录一下。
题目大意
给一个图，它是个DAG（有向无环图），它是个平面图，它有一个起点和一个终点。求最小的从起点到终点的路径数量，使得存在一组这么多路径可以覆盖这个图的每一条边。
做法 1：
首先，最小链覆盖让我们想到：最小点覆盖。
于是我们多设置 \(m\) 个点表示 \(m\) 条边，就转化为 最小可重路径点覆盖，然后拆点 + 二分图匹配即可。
具体的，我们将每个点 \(U\) 拆成 \(U_x\) 和 \(U_y\) 两个点。若 \(A\) 和 \(B\) 有边，那么就连接 \(A_x\) 和 \(B_y\)。容易发现，这样建立新图最后是一个二分图，那么 最小不可重路径点覆盖其实就是 原图的顶点数量 - 二分图最大匹配数。
对于 最小可重路径点覆盖 而言，我们考虑如果 \(u\) 可以从原图走到 \(v\)，那么就将 \(u\) 连向 \(v\)。可以发现，这样建图就可以转换为 最小不可重路径点覆盖 了。
这样的话可以完成 \(n \le 300\) 的题目。
做法 2：
发现上面的做法少用了一个性质：平面图。
偏序集中，我们考虑 Dilworth 定理：最长反链长度 等于 最小链覆盖个数。
根据下图感性理解一下，最长反链选择的“链”，在平面图里是一段相邻的平面，所以就考虑平面图的对偶图，对应上就是一段链！
所以如果建出对偶图，那么结果就是，对偶图的最长链，就可以考虑 DAG 上 dp。
但是如果要求出平面图的每一个面再暴力拓扑的话就太麻烦了，其实我们考虑将平面从左往右进行 dp，然后将 dp 的值存到右侧的边上，然后如果存在环的话，可以发现，我们能分成“左侧” 和 “右侧”，然后用左侧的边更新右侧的边即可。
时间复杂度是 O(n)，显然可以做到 \(n <= 10^5\) 的题目。
总结
-
首先是 Dilworth 定理，可以将平面图的最长链覆盖 转换为 其对偶图的最长链。
-
在平面图的对偶图上操作的时候，可以考虑从左往右的顺序，然后把一些信息存到边上，就实现起来容易一点。