「BC35」DZY Loves Topological Sorting

2015年3月30日3,0750
问题描述
一张有向图的拓扑序列是图中点的一个排列,满足对于图中的每条有向边(uv)uv,都满足u在排列中出现在v之前。 现在,DZY有一张有向无环图(DAG)。你要在最多删去k条边之后,求出字典序最大的拓扑序列。
输入描述
输入有多组数据。 (TestCase5) 第一行,三个正整数 n,m,k(1n,m105,0km). 接下来m行,每行两个正整数 u,v(uv,1u,vn), 代表一条有向边(uv).
输出描述
对于每组测试数据,输出一行字典序最大的拓扑序列。
输入样例
5 5 2 1 2 4 5 2 4 3 4 2 3 3 2 0 1 2 1 3
输出样例
5 3 1 2 4 1 3 2
Hint
数据1. 删除(2->3),(4->5)两条边,可以得到字典序最大的拓扑序列:(5,3,1,2,4).

题解

搬运官方题解

因为我们要求最后的拓扑序列字典序最大,所以一定要贪心地将标号越大的点越早入队。我们定义点i的入度为di。假设当前还能删去k条边,那么我们一定会把当前还没入队的dik的最大的i找出来,把它的di条入边都删掉,然后加入拓扑序列。可以证明,这一定是最优的。 具体实现可以用线段树维护每个位置的di,在线段树上二分可以找到当前还没入队的dik的最大的i。于是时间复杂度就是O((n+m)logn).

蒟蒻hzwer用了个堆来暴力。。。

 

avatar
  Subscribe  
提醒