#P1379. [Baltic2001]Postman
[Baltic2001]Postman
题目描述
邮局位于 号村庄。邮递员需要从村庄 出发并回到村庄 ,至少经过每个村庄和每条道路一次。道路为无向边,可以有重边和自环。保证所有村庄连通,且每个村庄的度数为 、 或 (自环对度数贡献 )。
第 个村庄有期望值 。若它是路线中第 个首次到访的村庄,村庄向邮局支付 元;此值为负时,表示邮局支付其相反数。邮局每经过一条道路向邮递员支付 元,重复经过也需再次支付。
求使邮局总收益最大的路线长度,即所经过道路的总次数。本题仅输出该长度。
输入格式
第一行两个整数 ,表示村庄数和道路数,。 接下来 行,每行一个整数 ,。 接下来 行,每行两个整数,表示道路两端的村庄编号。
输出格式
输出邮局收益最大时的路线长度。
样例输入
6 7
1
7
4
10
20
5
2 4
1 5
2 1
4 5
3 6
1 6
1 3
样例输出
7