问题2669--图上旅行(tour)

2669: 图上旅行(tour)

时间限制: 1 Sec  内存限制: 128 MB
提交: 40  解决: 20
[提交] [状态] [讨论版] [命题人:]

题目描述

BSNY在一个图上旅行,这个图由n个点和m条无向边构成,无重边无自环,保证连通。
现在BSNY从图中选择点S出发遍历图,要求不能连续经过同一条边(可以绕个环再经过之前的边),比如样例中的图,从1到2,可以2到4, 4到5, 5到2,然后2可以返回1。但从1到3,无法马上从3回到1。
每个点都有一个权值wi,BSNY每到一个点,可以获得该点权值,但只能获一次,重复到达该点,无法再次获得权值。BSNY想知道,如何走,可以使得获得的权值最大。

输入

第一行输入n, m
第二行输入n个点的权值wi
接下来m行,输入m条边
最后一行输入起点S

输出

输出可以获得的最大权值

样例输入 Copy

5 5
1 1 1 1 1
1 2
1 3
2 4
2 5
4 5
1

样例输出 Copy

5

提示

样例输入2:
10 12
1 7 1 9 3 3 6 30 1 10
1 2
1 3
3 5
5 7
2 3
5 4
6 9
4 6
3 7
6 8
9 4
9 10
6
样例输出2:
61
30%数据 1<=n<=100,  0<=m<=100
另有30%数据 m=n-1
100%数据 1<=n<=200000, 0<=m<=200000  0<=wi<=10^9

来源/分类