Pro.ID22124 TitleElectric Power Title链接http://10.20.2.8/oj/exercise/problem?problem_id=22124 AC0 Submit0 Ratio- 时间&空间限制描述Grid Computing is a hot topic these years. Many people have heard of it, but some are still confused about it. In fact, this concept came from the electric power grid. Within an electric power grid, power stations and power users are all connected to the grids. Power stations generate the electricity and input it into the grid. On the other hand, the users get electricity from the grid, unaware where it comes from. Grid Computing works in the similar way.
Electric power grids worked very well in the past one hundred years. Recently, a plan about building a new electric power grid in our province was being discussed by GDCPC (Guangdong Construction Power Committee). This grid will cover all the cities and supply the maximum electric power. The electric network has been constructed. The committee members are now discussing where the power stations should be located. This grid has the following features:
(1) All cities are within the network.
(2) There is at most one power station built within a city. Of course, it locates far away from the residential area.
(3) There is at most one connection between two cities.
(4) There may be some circles in the network, none of which contains more than three distinct cities. For example, the network in Figure 1 is allowed while the one in Figure 2 is not.
 Figure 1 Figure 2
(5) aking safety into consideration, if two cities are directly connected, they cannot both have power stations.
(6) Due to the environment condition of the cities, the output of each power station cannot exceed a limitation value. These values differ from city to city.
In order to provide the maximum electric power, the location of the power stations should be carefully selected. Now, it is your task to help the committee decide the cities in which power stations will be built.
输入There are multiple cases. The input format for each case is: The first line contains only one integer N ( 1 <= N <= 100 ) indicating the number of the city. There are N positive integers (not greater than 1000) in the second line. The i-th integer is the limitation value of the i-th city. And then there’s a number in a line indicating the number of edges, i. e. , the number of pairs of linked cities. The following lines will describe the structure of the network. Each line contains two integers k and m, indicating that the k-th city and the m-th city is directly connected. N = 0 indicates the end of input. 输出Description Grid Computing is a hot topic these years. Many people have heard of it, but some are still confused about it. In fact, this concept came from the electric power grid. Within an electric power grid, power stations and power users are all connected to the grids. Power stations generate the electricity and input it into the grid. On the other hand, the users get electricity from the grid, unaware where it comes from. Grid Computing works in the similar way.
Electric power grids worked very well in the past one hundred years. Recently, a plan about building a new electric power grid in our province was being discussed by GDCPC (Guangdong Construction Power Committee). This grid will cover all the cities and supply the maximum electric power. The electric network has been constructed. The committee members are now discussing where the power stations should be located. This grid has the following features:
(1) All cities are within the network.
(2) There is at most one power station built within a city. Of course, it locates far away from the residential area.
(3) There is at most one connection between two cities.
(4) There may be some circles in the network, none of which contains more than three distinct cities. For example, the network in Figure 1 is allowed while the one in Figure 2 is not.
Figure 1 Figure 2
(5) aking safety into consideration, if two cities are directly connected, they cannot both have power stations.
(6) Due to the environment condition of the cities, the output of each power station cannot exceed a limitation value. These values differ from city to city.
In order to provide the maximum electric power, the location of the power stations should be carefully selected. Now, it is your task to help the committee decide the cities in which power stations will be built.
Input There are multiple cases. The input format for each case is: The first line contains only one integer N ( 1 <= N <= 100 ) indicating the number of the city. There are N positive integers (not greater than 1000) in the second line. The i-th integer is the limitation value of the i-th city. And then there’s a number in a line indicating the number of edges, i. e. , the number of pairs of linked cities. The following lines will describe the structure of the network. Each line contains two integers k and m, indicating that the k-th city and the m-th city is directly connected. N = 0 indicates the end of input. Output For each case output one line containing one integer. It is the maximum electric power that the grid will provide. Sample Input 2
1 2
1
1 2
5
1 2 3 4 5
6
1 2
2 3
1 3
3 4
3 5
4 5
0 Sample Output 2
7 Source 样例输入2
1 2
1
1 2
5
1 2 3 4 5
6
1 2
2 3
1 3
3 4
3 5
4 5
0 样例输出2
7 作者 |
|Archiver|手机版|小黑屋|同和创作矩阵
( 粤ICP备20019636号-1 )
GMT+8, 2025-2-4 14:06 , Processed in 0.037351 second(s), 14 queries .
Powered by Discuz! X3.4 Licensed
© 2001-2017 Comsenz Inc.
