同和创作矩阵 › ›博文归档› 技术博文归档 › 查看内容

21633_Readingbooks

2022-5-16 18:20| 发布者: Hocassian| 查看: 24| 评论: 0|原作者: 肇庆学院ACM合集

摘要:

C:\Users\Administrator\Downloads\2019-10-12-10-14-4-89505707525300-Problem List-采集的数据-后羿采集器.html

Pro.ID

21633

Title

Reading books

Title链接

http://10.20.2.8/oj/exercise/problem?problem_id=21633

AC

Submit

Ratio

35.29%

时间&空间限制

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)

描述

In the summer vacation, LRJ wants to improve himself in computer science. So he finds out N books of computer science in the school library. The books are numbered from 0 to N-1.

To finish reading the i-th book, it takes LRJ time[i] minutes. But some books are similar in the content. If the i-th book and the j-th book are similar, then if LRJ has finished reading the i-th book, it will take him only 『time[j]/2』 minutes to finish reading the j-th book. Of course if LRJ has finished reading the j-th book, it will take him only 『time[i]/2』 minutes to finish reading the i-th book. Now you are asked to tell LRJ the minimal total time to finish reading all the N books.

注：『』这对符号表示"向下取整"。

输入

The first line contains two integers N ( 0 ≤ N ≤ 100 ) and M ( 0 ≤ M ≤ N(N-1)/2 ). N is the total number of books. M is the number of pairs which are similar.

Then the following N lines describe time[0], time[1], ..., time[N-1] ( 1 ≤ time[i] ≤ 10⁵ ).

Next comes M lines, each contains two integer (i, j), indicating that the i-th book and the j-th book are similar.

Input is ended by N=0 and M=0.

输出

Description

In the summer vacation, LRJ wants to improve himself in computer science. So he finds out N books of computer science in the school library. The books are numbered from 0 to N-1.

注：『』这对符号表示"向下取整"。

Input

The first line contains two integers N ( 0 ≤ N ≤ 100 ) and M ( 0 ≤ M ≤ N(N-1)/2 ). N is the total number of books. M is the number of pairs which are similar.

Then the following N lines describe time[0], time[1], ..., time[N-1] ( 1 ≤ time[i] ≤ 10⁵ ).

Next comes M lines, each contains two integer (i, j), indicating that the i-th book and the j-th book are similar.

Input is ended by N=0 and M=0.

Output

For each test case, just output the minimal total time on a single line.

Sample Input

2 1
6
10
0 1
3 2
1
2
3
0 1
1 2
3 1
2
4
6
0 1
0 0

Sample Output

11
3
10

Hint

For the first test case, if LRJ read the books in the order (0, 1), then the total time = 6+10/2=11; if in the order (1, 0), then the total time = 10+6/2=13.

Source

GDCPC 2008

样例输入

2 1
6
10
0 1
3 2
1
2
3
0 1
1 2
3 1
2
4
6
0 1
0 0

样例输出

11
3
10

提示

For the first test case, if LRJ read the books in the order (0, 1), then the total time = 6+10/2=11; if in the order (1, 0), then the total time = 10+6/2=13.