codeforces 510 C. Fox And Names

2015年12月9日 0 作者 CrazyKK

http://codeforces.com/contest/510/problem/C

题意:给定n个字符串。问是否存在一种字母顺序,使得这n个字符串的顺序满足字典序(自定义的)。如果有多种顺序,输出字典序(标准的)最小的。

思路:将字符串的关系处理成边的关系。每次对于第i个和第i+1个字符串,从前往后扫,直到不相等的那一位,设为k,然后连边,指向i+1。表明第i个字符串的第k位大于第i+1个字符串的第k位。如果没有不想等的。说明其中一个是另一个的字串。如果前者是后者的字串,那么不影响。如果后者是前者的字串,则不存在满足条件的字典序。然后做拓扑排序。由于有多种输出字典序(标准的)最小的方案。所以存点的时候用优先队列存。