OI康复训练 luogu 1983 车站分级 拓扑排序

这种水题先后读错n次题意,还链前没开好炸了内存,没想到邻接矩阵,QwQ。

bzoj 1093: [ZJOI2007]最大半连通子图 强联通分量 拓扑排序 DP

这题很容易看出来做法,实现起来也很简单。

首先我们考虑,他这个半联通子图这个概念非常不好处理,我们尝试把他转化一下。想一下,为了求一个最大的半联通子图,显然在一个强联通分量内,我们应该是依次经过某些点,走出一条路径,然后延伸到强联通分量外的路径上。这样子我们可以先求强联通分量,然后在新图上进行[……]

Read more

bzoj 4010: [HNOI2015]菜肴制作 拓扑排序 优先队列

我们考虑,字典序最小的方案不对的。但是倒序字典序最大的方案一定是对的。因为靠后的位置尽可能的被劣质的菜品占据了。所以我们加反边,然后拓扑排序即可。