前言
最后一道, 补了跑路
思路
原来是贪心, 那没救了
首先考虑不加边的时候怎么处理
显然我们可以用小根堆代替队列处理 \(\rm{topo}\) 序
那么我们如何使得这个答案变大
不难发现, 我们只要对于当前堆顶加一条入度, 就一定可以使得答案变大
但是由谁来连这一条边呢?
我们先不管, 把它丢进一个堆里面
我们考虑维护一个大根堆 \(q\) 和一个小根堆 \(p\) , \(p\) 维护当前所有入度为 \(0\) 的点, \(q\) 维护确定用一次操作给他入度 \(+1\) 的点
每次维护, 肯定是尝试把 \(p\) 中的点加入 \(q\) 中, 若你发现 \(p\) 中只有一个元素且该元素还比 \(q\) 的堆顶大, 那么显然是直接确定即可
否则我们考虑把 \(p\) 中的点加入 \(q\) 中直到操作次数不够或者 \(p\) 被清空
如果操作完之后, \(p\) 中还有点, 只能将其作为当前这一位的答案, 否则用 \(q\) 的堆顶来作为这一位的答案
具体理解的话, \(q\) 的堆顶我们用当前拓扑序的前一位来指向它, 就可以做到这一个位置放最大的序
具体的,
- 小根堆大小大于 \(1\)
若 \(K>0\) : 为当前堆顶添加入边 (打标记并放入大根堆中)
否则：删掉堆顶（与普通拓扑序相同） - 小根堆大小等于 \(1\)
若 \(K>0\) 且大根堆不为空且大根堆堆顶更大 : 为当前堆顶添加入边，删掉大根堆堆顶
否则：删掉堆顶 - 小根堆大小等于 \(0\)
删掉大根堆堆顶
总结
很聪明, 但不知道有什么用
当每日一练了, 开拓思维
有点屎, 建议看 luogu 题解
标签：NWRRC2015,入度,当前,堆顶,Graph,删掉,T3,堆堆,小根堆 From： https://www.cnblogs.com/YzaCsp/p/18679992