bzoj#P1952. [SDOI2010] 城市规划

[SDOI2010] 城市规划

题目描述

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

输入格式

输入第一行有两个整数 nnmm,表示 pigsty 城市里面有 nn 个小区,在 iPig 修整城市后有 mm 条无向边连接着 nn 个小区。

接下来一行有 nn 个正整数,第 ii 个正整数 hih_i 表示第 ii 个小区的和谐值为 hih_i

接下来 mm 行,每行两个正整数 aabb1a,bn1 \le a,b \le n),表示存在一条连接着小区 aa 和小区 bb 的无向边。

输出格式

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

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

样例说明 1

反和谐主义者选择的小区分别是小区 33(看守的小区是小区 11、小区 22 和小区 55)、小区 77(看守的小区是小区 44 和小区 66)和小区 99(看守的小区是小区 88),这样会损失的总和谐值为 3+3+11=173+3+11=17。 或者选择的小区分别是小区 11(看守的小区是小区 22 和小区 33)、小区 44(看守的小区是小区 55 和小区 77)和小区 99(看守的小区是小区 88),这样会损失的总和谐值为 2+4+11=172+4+11=17。 如果同时选择小区 33、小区 44 和小区 99,虽然损失的总和谐值为 1818,但是小区 33 和小区 44 都要派猪来看守小区 55,这不符合条件,故此方案不可行。

5 5
4 4 9 7 7
1 2
2 3
1 4
3 5
5 4
9

数据规模与约定

  • 对于 20%20\% 的数据,保证每个点不存在于任何一个环中;
  • 对于另外 30%30\% 的数据,保证图中只存在一个环;
  • 对于 100%100\% 的数据,有 n106n \le 10^6m2×106m \le 2 \times 10^6,所有的权值不超过 10310^3