A2149 | $Protect the school$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

学校有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

C++ 编辑器

输入

输出