Free DIY Tour 编写程序来实现

Problem Description
Weiwei is a software engineer of ShiningSoft. He has just excellently fulfilled a software project with his fellow workers. His boss is so satisfied with their job that he decide to provide them a free tour around the world. It's a good chance to relax themselves. To most of them, it's the first time to go abroad so they decide to make a collective tour.

The tour company shows them a new kind of tour circuit - DIY circuit. Each circuit contains some cities which can be selected by tourists themselves. According to the company's statistic, each city has its own interesting point. For instance, Paris has its interesting point of 90, New York has its interesting point of 70, ect. Not any two cities in the world have straight flight so the tour company provide a map to tell its tourists whether they can got a straight flight between any two cities on the map. In order to fly back, the company has made it impossible to make a circle-flight on the half way, using the cities on the map. That is, they marked each city on the map with one number, a city with higher number has no straight flight to a city with lower number.

Note: Weiwei always starts from Hangzhou(in this problem, we assume Hangzhou is always the first city and also the last city, so we mark Hangzhou both 1 and N+1), and its interesting point is always 0.

Now as the leader of the team, Weiwei wants to make a tour as interesting as possible. If you were Weiwei, how did you DIY it?

Input
The input will contain several cases. The first line is an integer T which suggests the number of cases. Then T cases follows.
Each case will begin with an integer N(2 ≤ N ≤ 100) which is the number of cities on the map.
Then N integers follows, representing the interesting point list of the cities.
And then it is an integer M followed by M pairs of integers Ai, Bi. Each pair of [Ai, Bi] indicates that a straight flight is available from City Ai to City Bi.

Output
For each case, your task is to output the maximal summation of interesting points Weiwei and his fellow workers can get through optimal DIYing and the optimal circuit. The format is as the sample. You may assume that there is only one optimal circuit.

Output a blank line between two cases.

Sample Input
2
3
0 70 90
4
1 2
1 3
2 4
3 4
3
0 90 70
4
1 2
1 3
2 4
3 4

Sample Output
CASE 1#
points : 90
circuit : 1->3->1

CASE 2#
points : 90
circuit : 1->2->1

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问

相似问题

0
齿轮旋转的转速的计算的一个难题,如何利用C语言正确的方式编写程序代码来实现的
0
信息论提到的熵的概念的一种计算的方式,怎么采用C程序编写设计代码的思想合理实现?
0
有障碍物的情况下的一个搬动的算法的计算,怎么采用C程序的语言编写代码的方式实现的?
0
矩阵的符号表示方法的问题,怎么利用C语言的代码程序编写的具体思路去实现的呢?
0
超立方体的的构造命题的算法,怎么采用C程序的语言代码编写的技术去实现?
0
计算输出第N个的幸运的数字,怎么利用C语言代码程序编写的过程实现的?
4
使用free -m命令,发现free状态的内存比available内存要大,应用程序无法全部申请free内存
1
free()释放内存出错,释放的指针指向的地址未变化
0
齿轮的交叉旋转问题的计算方法,怎么使用C语言的程序编写的过程的方式来实现的呢?
0
计算选手可以获得的最高的奖金的问题,怎么使用C语言的程序代码编写的实际的思路实现的
0
方块解锁游戏用程序编写来实现,怎么用C语言的程序的代码编写的方式具体的实现的思想是怎么样的
0
迷宫的寻找的路线的问题,要求使用C语言的程序的编写的设计的代码的过程的做法怎么才能实现的呢?
0
过桥的等待的一个问题,怎么使用C语言的程序的编写的过程的方式有效实现的做法
0
迷宫的寻找的路线的问题,要求使用C语言的程序的编写的设计的代码的过程的做法的实现
0
需要切割后从小件中获得最高利润,怎么用C语言的程序的编写代码的设计的思路来实现这个计算
1
关于c语言中free以及指针的问题
0
C程序编写问题:Galou is back!
1
C-Free显示运行程序错误怎么办?
0
Battery的程序的代码的编写
0
Tempus et mobilius Time and motion程序代码的编写