P2811 Protect the school

    • 3通过
    • 8提交
  • 题目提供者 Kwork
  • 评测方式 云端评测
  • 标签 图论 高性能
  • 难度 尚无评定
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目背景

    话说上回保安因为奶牛事件而搞得地位岌岌可危,所以他们决定好好看守这个学校,他们有一个计划。但是由于学校太大了,他们计划不好,所以找到上次帮他的你,请你解决他的苦难。然后他又可以开始了手机游戏之旅。

    题目描述

    学校有n个检查点,由于保安懒得动脑筋,他们决定在这n个检查点之间建立m条通道,由于学校的懒政以及军事化管理,这些路是单向的,逆向通过会被处分。保安们人手不够(游戏任务太多),他们决定只挑选一些点来站岗,由于保安身怀绝技,他可以!!瞬间通过任何他站岗点可以走到的路(直接点,可以瞬间到任何连通的点)!!。每一个检查点有一个值表示这个点的困难程度。为了保护学校,请你帮他们出个主意,保证一旦有一个检查点发生事件,都能有保安瞬间抵达。但是为了舒服和管理便利,请你告诉他们在使用最少的保安数量的情况下最小的困难总和。

    输入输出格式

    输入格式:

    第一行一个整数n,代表检查点数量。

    接下来一行n个整数,代表困难程度。

    接下来一行一个数m,表示道路的数量。

    接下来m行每行两个整数u,v代表u到v有一条单向通道。

    输出格式:

    两个整数。

    第一个整数表示最小困难和。第二个整数表示在保证最小困难和以及最少保安数量的条件下,可选的方案总数。

    输入输出样例

    输入样例#1: 复制
    5
    31619 26195 18669 1198 178
    4
    2 4
    3 5
    1 2
    4 1
    输出样例#1: 复制
    20045 1

    说明

    n<=10000,m<=30000,保证答案在longint/int 范围内

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。