• 如果您想对本站表示支持,请随手点击一下广告即可~
  • 本站致力于提供原创、优秀的技术文章~
  • 有任何疑问或建议 均可以在站点右侧栏处 通过各种方式联系站长哦~
  • POJ1094 – Sorting It All Out

    ACM-POJ EXP 198阅读 0评论

    全解题报告索引目录 -> 【北大ACM – POJ试题分类


    提示: 拓扑排序

    这道题有隐含这一信息,每输入一对关系,如果判定有结果,则可以忽略后面输入数据,即使后面输入数据能改变结果,也不用管。所以应该每输入一个关系就去更新当前的图,然后进行一趟拓扑排序。一旦产生结果,再对后面的数据处理下,就可以输出结果。


    下面罗列所有可能的情况(类似于状态机:

    一、当输入的字母全部都在前n个大写字母范围内时:

    (1)最终的图 可以排序:
      在输入结束前如果能得到最终的图(就是用这n个字母作为顶点,一个都不能少);
      而且最终得到的图 无环;
      只有唯一一个 无前驱(即入度为0)的结点,但允许其子图有多个无前驱的结点。
      在这步输出排序后,不再对后续输入进行操作

    (2)输出矛盾
      在输入结束前如果最终图的子图有环
      在这步输出矛盾后,不再对后续输入进行操作

    (3)输出无法确认排序
      这种情况必须全部关系输入后才能确定,其中又有2种可能
        ① 最终图的字母一个不缺,但是有多个 无前驱结点
        ② 输入结束了,但最终的图仍然字母不全,与 无前驱结点 的多少无关

    二、当输入的字母含有 非前n个大写字母 的字母时(超出界限):

    (1) 输出矛盾
      输入过程中检查输入的字母(结点),若 前n个大写字母 全部出现,则在最后一个大写字母出现的那一步 输出矛盾

    (2) 输出无法确认排序
      最后一步输入后,前n个大写字母 仍然未全部出现,则输出 无法确认排序


    注意:

    在使用“无前驱结点”算法时必须要注意,在“矛盾优先”的规律下,必须考虑一种特殊情况,就是多个无前驱结点与环共存时的情况,即输入过程中子图都是有 多个无前驱结点,最后一步输入后出现了环,根据算法的特征,很容易输出“不能确认排序”,这是错的,必须适当修改算法,输出“矛盾”。

    例如:

    6 6

    A<F

    B<D

    C<E

    F<D

    D<E

    E<F

    输出矛盾

    转载请注明:EXP 技术分享博客 » POJ1094 – Sorting It All Out

    喜欢 (0) 分享 (0)
    发表我的评论
    取消评论

    表情

    Hi,您需要填写昵称和邮箱!

    • 昵称 (必填)
    • 邮箱 (必填)
    • 网址