zcmimi's blog

arrow_backdag共1篇文章

avatar
zc
2019-12-31 11:31:00
查看原题

点击跳转

这个图是个DAG,我们可以很快地处理出每个点以他为起点(ds_i)或终点(dt_i)的最长路

接着我们枚举删掉哪个点

我们可以将拓扑序小于当前点的点称作A集合,大于的称作B集合

删掉这个点后的最长路有三种可能:

A\rightarrow A,A\rightarrow B,B\rightarrow B

(to指x连接的点)

当删除一个点x时,我们可以删去所有集合中的dt_to+1+ds_x(反向图中的)

求出集合中的最大值就是当前最长路长度

接着将dt_x+1+ds_to加入集合,转移到下一个状态(原图中的)

于是我们需要一个数据结构满足以下要求:

  1. 插入某个值
  2. 删除某个值
  3. 查找最大值

我们可以用堆(手写堆或者两个stl优先队列)、平衡树、权值线段树等维护

1/1
Search
search