#P1453. 城市环路
城市环路
题目背景
一座城市,往往会被人们划分为几个区域,例如住宅区、商业区、工业区等等。
B 市就被分为了以下的两个区域——城市中心和城市郊区。在这两个区域的中间是一条围绕 B 市的环路,环路之内便是 B 市中心。
题目描述
整个城市可以看做一个 个点, 条边的单圈图(保证图连通),唯一的环便是绕城的环路。保证环上任意两点有且只有 条简单路径互通。图中的其它部分皆隶属城市郊区。
现在,有一位名叫 Jim 的同学想在 B 市开店,但是任意一条边的 个点不能同时开店,每个点都有一定的人流量,第 个点的人流量是 ,在该点开店的利润就等于 ,其中 是一个常数。
Jim 想尽量多的赚取利润,请问他应该在哪些地方开店?
输入格式
第一行一个整数 ,代表城市中点的个数。城市中的 个点由 编号。
第二行有 个整数,第 个整数表示第 个点的人流量 。
接下来 行,每行有两个整数 ,代表存在一条连接 和 的道路。
最后一行有一个实数,代表常数 。
输出格式
输出一行一个实数代表答案,结果保留一位小数。
4
1 2 1 5
0 1
0 2
1 2
1 3
2
12.0
提示
数据规模与约定
- 对于 的数据,保证 。
- 另有 的数据,保证环上的点不超过 个。
- 对于 的数据,保证 ,,,, 的小数点后最多有 位数字。