编程介的小学生 2017-09-19 09:36 采纳率: 20.5%
浏览 694
已采纳

Space AI Bombs

Description

The time is year 3000. Human beings have settled on planets in many solar systems and have a star war with an alien species called Romulans. The human scientists design a new weapon called AI bomb which is capable of space travel across the vast space. Before launching the weapons, humans send probes to collect Romulan's defense parameters. The data shows that Romulans have set up shields in the routes to their home worlds. Fortunately, some secret information reveals that the shield can be penetrated using an ion beam with a particular range of frequency. It is possible to pass the shield if an AI bomb emits an ion beam within that frequency. Now,human scientists have plotted an interstellar map between several human planets and Romulan planets. The map is a directed graph like Figure 4. In the figure, human planets are drawn in boxes (denoted as Hx) and Romulan worlds are drawn in triangles (denoted as Rx), where x is an integer number. A shield is drawn as a circle in the figure (denoted as Sx).
Since humans only know where the shields are but do not know the frequency of each shield, they decide to launch a large number of AI bombs. Each bomb is configured to emit an ion beam at a particular frequency at first. Once an AI bomb passes a shield, it will modulate its frequency to a different value by increasing or decreasing a predefined value. For example, in Figure 4, an AI bomb B1 is launched from H3 with initial frequency 150 and an interval (+/-) 100. So, when B1 penetrates shield S5, it may modulate its frequency to 50, 250, or keep its previous frequency 150. After that, the bomb can choose any routes available in the star map. In the example, the bomb B1 is possible to reach Romulan homeworld R9 by penetrating S5

with the original frequency 150 and then passing S4 by changing its frequency to 250 and keeping frequency 250 to pass S5 again and by changing its frequency to 350 in order to penetrate S7 and then finally nuking Romulan planet R9.
Unfortunately, Romulans knows what humans are planning. Their spies got the map and the bomb parameters. Of course, Romulans have shield parameters at hand.They want to know if there are any AI bombs which can reach their homeworlds under current shield settings. Please note that human AI bombs can choose any route to travel. If an AI bomb has any chance to reach a Romulan's home world, then the bomb must be reported.
Please write a program for the Romulan to defend vicious humans. To simplify the problem, we restrict the frequency values between 0 and 1000. When a bomb's new frequency is outside the range, the new frequency is invalid.
Input

The test data begins with a number n in a line which is the number of test cases. In each test case, it begins with two numbers v and e in a line where v is the number of vertices (including human planets, Romulan planets, and shields) and e is the number of directed edges, 2<= v <= 100000 and 2 <= e <= 500000. For convenience,
the vertices are indexed starting with 1.
Next, a line beginning with 'human m' tells that there are m human planets. Following the string are m integers, which are the indices of human planets.
Same as above, a string 'romulan k' is used to tell the vertex indices of Romulan's planets.
A string 'shield x' begins the shield parameters, where x is the number of shields.
Each shield parameter is described by (s l u), where s is the shield's index, l is the lower bound of the range, and u is the upper bound of the range. The values of l and u is between 0 and 1000.
A string 'edge u' begins the directed edge data, where u is the number of edges.Each edge is described by (s d), where s is the index of the source vertex and d is the index of end vertex.
A string 'bomb p' begins with the data of deployed AI bombs, where p is the number of bombs and 1 <= p <= 10000. Each bomb is described by (h f i), where h is the index of a vertex (i.e., a human planets where the bomb is located), f is the initial frequency,and i is the interval to be increased/decreased.
Output

Please output the number of bombs that can possibly reach any of the Romulan homeworlds in one line for each test case. Note that, a bomb may be able to reach more than one Romulan planets. In that case, it is still counted as 1.
Sample Input

1
9 9
human 3 1 2 3
romulan 2 8 9
shield 4
4 200 400
5 100 300
6 100 200
7 350 500
edge 9
1 6
6 8
2 4
4 6
4 5
5 4
3 5
5 7
7 9
bomb 2
3 150 100
2 250 50
Sample Output

2

  • 写回答

1条回答 默认 最新

  • threenewbee 2017-10-04 16:10
    关注
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

悬赏问题

  • ¥15 求差集那个函数有问题,有无佬可以解决
  • ¥15 【提问】基于Invest的水源涵养
  • ¥20 微信网友居然可以通过vx号找到我绑的手机号
  • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
  • ¥15 解riccati方程组
  • ¥15 display:none;样式在嵌套结构中的已设置了display样式的元素上不起作用?
  • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
  • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
  • ¥50 树莓派安卓APK系统签名
  • ¥65 汇编语言除法溢出问题