A2149. Protect the school
编程题
提高+/省选-
知识点
题目描述
学校有n个检查点，保安决定在这n个检查点之间建立m条通道，这些路是单向的。保安们人手不够，他们决定只挑选一些点来站岗。保安可以随时支援任何站岗点。每一个检查点有一个值表示这个点的困难程度。为了保护学校，请你帮他们出个主意，保证一旦有一个检查点发生事件，都能有保安瞬间抵达。但是为了舒服和管理便利，请你告诉他们在使用最少的保安数量的情况下最小的困难总和。
输入格式
第一行一个整数n,代表检查点数量。
接下来一行n个整数，代表困难程度。
接下来一行一个数m，表示道路的数量。
接下来m行每行两个整数u，v代表u到v有一条单向通道。
接下来一行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 范围内