Dotcpp  >  编程题库  >  蓝桥杯2022年第十三届决赛真题-宝石收集(Java组)
题目 2726:

蓝桥杯2022年第十三届决赛真题-宝石收集(Java组)

时间限制: 2s 内存限制: 256MB 提交: 17 解决: 6

题目描述

小蓝最近迷上了一款收集宝石的游戏,在游戏中给出了一幅藏宝图,藏宝图可以看做是由 n 个顶点组成的一个有向图,顶点编号为 0, 1, 2, · · · , n − 1。每个顶点有且仅有一颗宝石,可能是红宝石或蓝宝石。

小蓝有一次收集宝石的机会,他可以任意选择一个顶点当做起点,沿着有向边前进,经过的顶点上的宝石都会被自动收集(包括起点和终点),直到前方无路可走或者小蓝想退出时停止本次收集。小蓝可以多次经过同一个顶点,但只会在第一次到达顶点时获得宝石,后面再次到达时不会再获得宝石。

收集结束后,小蓝可以用手中的宝石合成紫晶宝石:一颗红宝石加一颗蓝宝石就可以合成一颗紫晶宝石。

小蓝想在收集结束后合成尽可能多的紫晶宝石,请帮他规划出一条最优路径,告诉他最多可以合成多少颗紫晶宝石。

输入格式

输入的第一行包含一个整数 n,表示有顶点的个数。

第二行包含一个由 0、1 组成的长度为 n 的字符串,从左至右依次表示第 0 至 n − 1 个顶点处宝石的种类,0 表示红宝石,1 表示蓝宝石。

第三行包含一个整数 m ,表示图中有 m 条有向边。

接下来 m 行,每行包含两个整数 s, t ,用一个空格分隔,表示一条从 s 到 t 的有向边。

输出格式

输出一行包含一个整数,表示小蓝最多能合成几颗紫晶宝石。

样例输入

6
000111
6
0 1
1 2
3 1
2 3
2 4
2 5

样例输出

2

提示

样例如上图所示,选择 0 号顶点作为起点,按照 0 → 1 → 2 → 3 → 1 → 2 → 4 的行进路线,可以获得 3 颗红宝石和 2 颗蓝宝石,最终可以合成 2 颗紫晶宝石;他也可以按照 1 → 2 → 3 → 1 → 2 → 4 行进,结果也是 2 。找不到比 2 更大的答案了。

对于所有的评测用例,1 ≤ n ≤ 2000 ,0 ≤ m ≤ 105 ,0 ≤ s ≤ n − 1 ,0 ≤ t ≤ n − 1。

标签