经典问题 1 —— DAG 上区间限制拓扑序
2024-10-20 08:35:44
问题描述
给定一个 DAG,求一个拓扑序,使得节点 \(i\) 的拓扑序 \(\in [l_i,r_i]\)。
题解
首先进行一个预处理:对于所有 \(u\),令 \(\forall (v,u)\in E, l_u\leftarrow \max(l_u,l_v+1),\forall (u,v)\in E, r_u\leftarrow \min(r_u,r_v-1)\)。
也就是 \(l_u\) 对任何可能的拓扑序的最小值取 \(\max\),\(r_u\) 同理。若此时有节点 \(l_u>r_u\) 则无解。
将所有区间按 \(r\) 端点排序,然后以 \(l\) 端点为关键字插入大根堆中。从大到小依次考虑拓扑序 \(i\) 应为哪个节点,将所有 \(r_u\ge i\) 的节点插入堆中,然后取出 \(l_u\) 最大的,若 \(l_u>i\) 则显然无解,否则直接令 \(topo_i=u\),弹堆。由贪心交换性质应该可以证明这是可能的最优情况,如果这样都无解那么一定无解。至于正确性,我们发现如果当前存在 \(j>i\) 使得 \((topo_j,topo_i)\in E\),则会有 \(l_{topo[i]}>l_{topo[j]}\),与每次取出 \(l\) 最大的区间矛盾。
最新文章
- Gridview中几个Button的应用
- 两种读写配置文件的方案(app.config与web.config通用)
- HTTP状态码206和416
- Greenplum获取表结构
- GIT(分布式版本控制系统)
- java中Date与String的相互转化
- android 6.0(api 23) SDK,不再提供org.apache.http.*(只保留几个类)
- 数学+高精度 ZOJ 2313 Chinese Girls' Amusement
- Android Volley 框架的使用(一)
- android用NDK编译出so最简单的方法
- vb.net中的SqlHelper
- Windows 之 删除文件出现“该项目不在请确认该项目的位置”
- c/c++读取文件
- css hr 设置
- 【Swift】—— 中国课程
- Zend server最大化应用程序的性能、扩展性和可用性
- Android 插件化技术窥探
- C#微信支付对接
- mysql----------利用navicat查看两个数据库之间的差异
- 单周期CPU设计的理论基础