5952: BZOJ1952：[Sdoi2010]城市规划

小猪iPig来到了一个叫做pigsty的城市里，pigsty是一座专门为小猪所准备的城市，城市里面一共有n个小区给小猪们居住，并且存在许多条无向边连接着许多小区。因为这里是一个和谐的城市，所以小猪iPig准备在这个城市里面度过他的余生。 若干年之后小猪iPig当上了规划局长，这件事令他非常开心。不过与此同时pigsty城市里面出现了许多反和谐主义者，他们已经厌烦了这样和谐的生活，在城市里到处闹事。小猪iPig为了更好地控制局面，他把城市改造成了另外一个样子：iPig把道路全部摧毁之后重新修建了m条无向边，并且保证每一个小区最多存在于一个由无向边组成的环中。 iPig以为这样做就让那些反和谐主义者不敢继续猖狂下去了，谁知到在新的城市道路修建好以后反和谐主义者宣言要对城市的小区进行一次洗脑！ 这下可麻烦了，iPig赶紧收集了许多的情报。iPig给每个小区标记了一个和谐值HX_i，用它来表示第i个小区的和谐程度。 通过地下消息iPig又得知那些反和谐主义者进攻时有个规律：他们会选择若干个小区下手，这些小区都派一只猪过去，把这些小区的和谐值归零。在这个过程中，每个选择的小区所直接连接着的几个小区都派了一只猪去看守——以防被警猪给干扰。这个计划看似完美但是还是存在一个漏洞：因为人员之间都是在网络上认识的，互相没有见过面，为了防止不必要的麻烦（认错猪之类），每个小区最多只会有一头猪存在。 iPig突然感到了莫大的压力，他想知道在最坏情况下会丢失多少和谐值。但是不懂计算机的他不知道应该怎样计算。你能帮帮他吗？

输入格式

输入第一行有两个整数n和m，表示pigsty城市里面有n个小区，在iPig修整城市后有m条无向边连接着n个小区。 接下来一行有n个正整数，第i个正整数HX_i表示第i个小区的和谐值为HX_i。 接下来m行，每行两个正整数a和b（1<=a,b<=n），表示存在一条连接着小区a和小区 b的无向边。

输出格式

输出只有一行一个整数，表示最坏情况下损失的和谐值为多少。

样例输入

9 9
2 2 3 4 1 2 3 10 11
1 2
2 3
1 3
3 5
5 4
5 6
4 7
6 7
8 9

样例输出

17

【样例解释】
反和谐主义者选择的小区分别是小区3（看守的小区是小区1、小区2和小区5）、小区7（看守的小区是小区4和小区6）和小区9（看守的小区是小区8），这样会损失的总和谐值为3+3+11=17。
或者选择的小区分别是小区1（看守的小区是小区2和小区3）、小区4（看守的小区是小区5和小区7）和小区9（看守的小区是小区8），这样会损失的总和谐值为2+4+11=17。
如果同时选择小区3、小区4和小区9，虽然损失的总和谐值为18，但是小区3和小区4都要派猪来看守小区5，这不符合条件，故此方案不可行。

【数据约定】
对于20%的数据，保证每个点不存在于任何一个环中；
对于另外30%的数据，保证图中只存在一个环；
对于100%的数据，有N<=1000000，M<=2000000，所有的权值不超过1000。

提示

没有写明提示

题目来源

没有写明来源