CF274D Lovely Matrix

题目描述

给出一个矩阵,其中有些位置已经填好了数,有些位置的数没填好(但是你可以任意填)。你可以填上这些空之后交换矩阵中的列,问是否能交换成一个每行的数都单调不增的矩阵。

分析

矩阵中的数可以相等,因此我们只需要考虑已经填好的数之间的限制就好了。
最简单的想法当然是排序后,相邻的两个元素从小的向大的连边,然后拓扑排序。考虑到所有的限制,这样连边是平方级别的,空间和时间都不能承受。
这是候我们用到一个技巧:加入一个虚点(据说这个技巧最初出现在网络流中)。就比如,对于两端相邻的数:a_i,a_{i+1},…,a_j,a_{j+1},…,a_k,且a_i=a_{i+1}=…=a_j, a_{j+1}=…=a_k,我们一开始对于a_ia_j中的点都会与a_{j+1}a_k中的点两两连一条边;这时候我们加入一个虚点u,将a_ia_j中的点都连一条到u的边,从ua_{j+1}a_k中的点都连一条边。这样边数的级别就降到了线性的。

总结

加入虚点,图的本质并没有发生变化,但是时空复杂度有了质的优越。这是一个非常好的技巧。

About The Author

发表评论

电子邮件地址不会被公开。 必填项已用*标注