关于二维偏序的建图构造(
  • 板块学术版
  • 楼主_ztyqwq
  • 当前回复7
  • 已保存回复7
  • 发布时间2020/8/24 14:35
  • 上次更新2023/11/6 19:31:00
查看原帖
关于二维偏序的建图构造(
73645
_ztyqwq楼主2020/8/24 14:35

平面上有 nn 个点,求连若干有向边,使得

(a,b)(c,d)ac,bd(c,d)可以直接或间接连向(a,b)\forall (a, b)(c, d)\quad a \leqslant c, b \leqslant d \Leftrightarrow (c, d) \text{可以直接或间接连向} (a, b)

可以添加若干个辅助点,间接连向即通过一条有向边组成的路径可以连向,显然该图是一个 DAG

求构造 QAQ

2020/8/24 14:35
加载中...