欢迎光临散文网 会员登陆 & 注册

Educational Codeforces Round 100 E.Plan of Lectures 缩点+拓扑排序

2022-07-12 17:14 作者:Asunataisiki  | 我要投稿

题意:有一个人要讲n门课,但是每门课a%5Bi%5D之后才能讲,若a%5Bi%5D%3D0则没有需要提前讲的,并且现在还有m个条件,每个条件给出x_ix_i%20%5Cneq%20x_j表示x_i之后的一门课必须是y_i保证 x_i%5Cneq%20x_j y_i%5Cneq%20y_jn门课的顺序是否有解


思路:条件一相当于给了我们一棵树,注意条件二的限制条件,表明给出的关系一定是若干条链,并且要求相邻,那么这一条件我们就可以进行缩点,而答案显然在图上有着明显的先后顺序,那么我们在新图上跑一次拓扑排序便是答案了。


注意:无解的情况,新图中有环,条件二的顺序与条件一中树的顺序不同(如条件二要求 1 -> 3, 而条件一中是3 -> 1),条件二中产生了环

具体细节见代码注释


Educational Codeforces Round 100 E.Plan of Lectures 缩点+拓扑排序的评论 (共 条)

分享到微博请遵守国家法律