危机火车

文章
5
资源
0
加入时间
2年10月27天

agc010_e Rearranging (图论建模 贪心 拓扑序)

最后做法挺简单的,但确实不容易想到这么多大胆的步骤。首先第一眼就能发现Takahashi的序列中如果存在,那么和的相对位置永远不会改变,也就相当于永远在后面出现。思维比较发散的人可能已经想到了拓扑——连一条边,这样就形成了一个DAG,Aoki肯定会按最大字典序来访问这个拓扑图。所以我们其实是给一个无向图(  就给i和j连边)确定方向,变成有向图,使得最后最大拓扑序最小(我们称之为“最优序列”)...