3681: 划分城镇-【2014暑期训练】T4Day1T3

划分城镇

【问题描述】

已知某县有n个村庄(1<=n<=100),其中县城也视为一个村庄），每个村庄间有且仅有一条路径连接。已知每个村庄的人数及村庄间的连接情况。先需要将该县划分为k个（1<K<n）乡。令sum(i)表示第i个乡中所有村庄的人数和（1<=i<=k）,x为最小乡的人数和。

寻找满足如下条件的划分方案：

（1）   每一乡中的村庄必然是直接或者间接地和其他村庄相连接；

（2）   划分方案对应的x尽可能地大。

【文件输入】

输入文件town.in。

第一行两个正整数n和k，分别表示村庄数和要划分的乡数；

第二行为n个整数，依次为每个村庄的人数；

第三行为村庄间连接的边数m；

接下来m行，每行两个正整数ai,bi(1<=i<=n)，表示每条边连接的一对村庄。

【文件输出】

输出文件town.out。

一行一个整数，表示最大的X值。

【输入样例】

8 4

3 9 3 6 3 5 12 4

7

1 2

1 3

1 4

2 5

2 6

3 7

4 8

【输出样例】

6