OI题库

【问题描述】
网格计算是近年来的热门话题之一，许多人听说过，但并不清楚它的具体内容。事实上，
这一思想来源于电力供应网，发电站和用户都连接在电力网中。发电站发电并把它输入到电
网中，用户从电网中用电而不需要知道电来自于哪里。网格计算也是类似的工作原理。
电力网己经有一百多年的使用了，最近正在尝试一种新型的电力网，它能覆盖一定范围
内的所有城市并提供最大的电量。该电力网具有以下特点：
1 所有城市均在电力网内；
2 一个城市至多有一个发电站，当然它应该远离住宅区；
3 两个城市间至多有一条电力线路相连；
4 电力网中可能存在圈，但任何一个圈中包含的城市个数不超过 3 个；
5 基于安全方面的考虑，如果两个城市直接相连．则他们不能同时拥有发电站；
6 每个城市的发电站都有各自能提供的最大电量。
编写程序求该电力网能提供的最大电量。
【输入】(electric.in)
第一行：一个正整数 N ( 1 <= N <= 100 ) ，表示电力网内城市的总个数；
第二行： N 个正整数(不超过 1000 ) ，表示各个城市的发电站能提供的最大电量；
第三行：一个正整数 M ，表示电力网中的线路的数量；
以下 M 行：每行两个数，中间用空格隔开，表示线路连接的两个城市。
【输出】(electric.out)
一个数：电力网所能提供的最大电量。
【样例输入】
5
1 2 3 4 5
6
1 2
2 3
1 3
3 4
3 5
4 5
【样例输出】
7